2014 dxdy logo

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

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





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


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

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

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



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

Сейчас этот форум просматривают: Andrey A


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

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