2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки





Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3
 
 Re: Задача вроде бы на Минимальные Остовные Деревья
Сообщение07.02.2015, 18:48 


13/05/14
231
Skeptic
Skeptic в сообщении #975076 писал(а):
Минимальный кандидат - это граф с одним внутренним ребром и двумя граничными. Поэтому сочетание по три элемента, а не по два.

Но ведь у ребра две концевые вершины и, следовательно, может быть еще пара смежных с ним ребер (но с другой стороны)
Skeptic в сообщении #975022 писал(а):
Линейный граф - это граф, рёбра которого можно вытянуть в линию.

А что значит "ребра вытянуть в линию"? Может быть Вы подразумевали "расположить ребра на одной линии". Но тогда этому определению соответствует простая цепь. Вы это имели в виду?
Skeptic в сообщении #975076 писал(а):
Плоский граф - это граф, который можно расположить на плоскости без пересечения рёбер.

Если быть точным, граф, который можно расположить на плоскости без пересечения рёбер обычно называется планарным. Плоский граф - это уже уложенный на плоскости граф.
Skeptic в сообщении #975022 писал(а):
$N$-мерный граф - это, понятно, какой граф.

Это граф с $n$ ребрами?

 Профиль  
                  
 
 Re: Задача вроде бы на Минимальные Остовные Деревья
Сообщение07.02.2015, 19:32 


10/05/13
251
Терминология теории графов богата. Но в этом топике мы не это выясняем, а решаем задачу. (Еще несколько постов не касающиеся темы и понять невозможно будет что мы тут хотели обсуждать) :D

 Профиль  
                  
 
 Re: Задача вроде бы на Минимальные Остовные Деревья
Сообщение07.02.2015, 19:46 


13/05/14
231
frankenstein
Я согласен с Вами. Но если давать советы, то их надо четко формулировать....
... Если все-таки перейти к реберным графам, то задача сводится к поиску компонент связности, состоящих из вершин с одинаковыми весами, окруженных вершинами с меньшими весами.
Что-то похоже на задачу: дана матрица из 0 и 1. Найти квадратную(прямоугольную) подматрицу из одних единиц. Где-то видел, но не могу найти :D

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 33 ]  На страницу Пред.  1, 2, 3

Модераторы: Toucan, maxal, Karan, PAV, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group