Форум программистов, компьютерный форум, киберфорум
Наши страницы
Дискретная математика
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/6: Рейтинг темы: голосов - 6, средняя оценка - 5.00
Lilu666
35 / 35 / 30
Регистрация: 25.04.2012
Сообщений: 74
1

Граф типа дерево

30.01.2013, 17:57. Просмотров 1121. Ответов 11
Метки нет (Все метки)

Как по матрице инциденции определить, что граф является типом "дерево"? Какие конкретно есть признаки? Мне нужно написать программку на паскале.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.01.2013, 17:57
Ответы с готовыми решениями:

Существует ли граф дерево с заданным значениями радиуса и диаметра
Радиус графа 3 а диаметр 4 если не существует то почему

Граф общего типа -- что это?
Добрый вечер. Суть моего задания, это написать программу, которая бы реализовала некоторую...

Как преобразовать неориентированный граф в ориентированный граф из матричной записи
Есть ли какой нибудь алгоритм преобразования Неориентированный графа в ориентированный граф из...

Ориентированный граф задан матрицей смежности. Нарисовать граф с наименьшим количеством пересечений
Ориентированный граф задан матрицей смежности. Нарисовать граф с наименьшим количеством...

Граф типа дерево
Как по матрице инциденции определить, что граф является типом "дерево"?

11
Mysterious Light
Эксперт по математике/физике
4094 / 2003 / 410
Регистрация: 19.07.2009
Сообщений: 3,022
Записей в блоге: 22
30.01.2013, 20:03 2
Если граф неориентированный, то деревом будет т. и т. т., когда он ацикличен и связан. Можно проверить связность, ровно как и ацикличность, это стандартные задачи для графов.
1
Lilu666
35 / 35 / 30
Регистрация: 25.04.2012
Сообщений: 74
30.01.2013, 20:11  [ТС] 3
Цитата Сообщение от Mysterious Light Посмотреть сообщение
Если граф неориентированный, то деревом будет т. и т. т., когда он ацикличен и связан. Можно проверить связность, ровно как и ацикличность, это стандартные задачи для графов.
Так, ацикличный и связанный. А как по матрице инциденции это определить?
А если граф ориентированный?
0
iifat
2392 / 1543 / 136
Регистрация: 05.06.2011
Сообщений: 4,318
31.01.2013, 09:17 4
Возвести в n-ю степень (n -- размерность), заменив + на max. Далеко не самый быстрый способ, но, пожалуй, самый простой. Если будет хоть одна единица -- цикл.
1
31.01.2013, 09:17
Lilu666
35 / 35 / 30
Регистрация: 25.04.2012
Сообщений: 74
31.01.2013, 09:52  [ТС] 5
Цитата Сообщение от iifat Посмотреть сообщение
Возвести в n-ю степень (n -- размерность), заменив + на max. Далеко не самый быстрый способ, но, пожалуй, самый простой. Если будет хоть одна единица -- цикл.
Не совсем понимаю, что возводить в степень. Вот я написала программку, которая рандомно задает сначала матрицу смежности, а из нее выводит матрицу инцидентности. Типа такой:
Pascal
1
2
3
4
 1 -1  0  0 -1
 0  1  2  1  0
 0  0  0  0  1
-1  0  0 -1  0
Как по этой матрице определить, что есть цикл? Петель не должно быть (двоек), это я понимаю.
Честно говоря, не хочется сильно вникать в теорию графов, задачка-то на программирование.
0
iifat
2392 / 1543 / 136
Регистрация: 05.06.2011
Сообщений: 4,318
31.01.2013, 10:05 6
А, возводить в степень надо как раз матрицу смежности. Перепутал.

Добавлено через 5 минут
Ну, подозреваю, ищи стандартные алгоритмы поиска по графу -- поиск в глубину и поиск в ширину...
0
Mysterious Light
Эксперт по математике/физике
4094 / 2003 / 410
Регистрация: 19.07.2009
Сообщений: 3,022
Записей в блоге: 22
31.01.2013, 14:30 7
Только что в голову пришла такая банальная мысль:
Если граф ориентирован, в его матрице инцидентности в каждом столбце сумма будет равна 0, потому что будет ровно по одной -1 (начало дуги) и 1 (конец дуги), остальные нули.
Тогда корень дерева будет выделяться среди остальных тем, что в его строке будуть только исходящие дуги, то есть только 0 и -1. Это простой и эффективный критерий корня: в матрице должна быть ровно одна такая строка.
Далее находим все смежные вершины, они должны быть корнями поддеревьев, поэтому в соответствующих строчках должна быть одна 1 (входящая дуга от корня), -1 и 0.

Набросок:
  1. Проверяем, что в каждом столбце ровно одна 1 и одна -1, остальные нули.
  2. Проверяем, что в каждой, кроме одной, строке ровно одна 1.
  3. Рассматриваем строку, в которой нет 1.
  4. Отмечаем вершину как «достигнутую».
  5. Ищем всех соседей для рассматриваемой вершины (строки).
    1. Для этого ищем все -1 на этой строке. Их число определяет внешнюю степень (out-degree) рассм. вершины.
    2. В каждом столбце, на котором находится -1 в рассматриваемой строке в прошлом шаге, ищем 1.
    3. Соответствующая строка является соседом рассматриваемой вершины.
  6. Для каждого соседа рекурсивно вызываем шаг 4.
  7. Если не пройдена проверка из первых пунктов или остались какие-то неотмеченные вершины, то перед нам — не дерево.
Более того, мы можем сказать так:
Если провалилась первая проверка — перед нами не матрица инцидентности или имеются петли или ещё что-то неоговорённое.
Если провалилась вторая проверка — перед нами не дерево, потому что либо нет корня вообще, либо более одной вершины имеют нулевую in-degree, либо имеются вершины с in-degree больше 1.
Если остались неотмеченные вершины, то они не связанны с корнем — граф несвязанный.
1
iifat
2392 / 1543 / 136
Регистрация: 05.06.2011
Сообщений: 4,318
31.01.2013, 15:50 8
Где-то в области шагов 5.ii-5.iii надо проверить, что эти соседи ещё не помечены как достигнутые -- это проверка на циклы. Ну, или шаг 4 начать с этой проверки.
На шаге 6 рекурсивно вызываем шаги 4-6.
2
Mysterious Light
Эксперт по математике/физике
4094 / 2003 / 410
Регистрация: 19.07.2009
Сообщений: 3,022
Записей в блоге: 22
31.01.2013, 18:33 9
Цитата Сообщение от iifat Посмотреть сообщение
Где-то в области шагов 5.ii-5.iii надо проверить, что эти соседи ещё не помечены как достигнутые -- это проверка на циклы. Ну, или шаг 4 начать с этой проверки.
Это имеет смысл.
0
Lilu666
35 / 35 / 30
Регистрация: 25.04.2012
Сообщений: 74
31.01.2013, 19:08  [ТС] 10
Спасибо! Осталось только разобраться, что к чему

Цитата Сообщение от Mysterious Light Посмотреть сообщение
1. Проверяем, что в каждом столбце ровно одна 1 и одна -1, остальные нули.
Ну это понятно, иначе это была бы не матрица инциденции.

Цитата Сообщение от Mysterious Light Посмотреть сообщение
2. Проверяем, что в каждой, кроме одной, строке ровно одна 1.
Это значит, что в каждую вершину должен быть только 1 вход.

Цитата Сообщение от Mysterious Light Посмотреть сообщение
3. Рассматриваем строку, в которой нет 1.
Это как понять? Если нет единиц, то это как бы корень дерева получается?

Цитата Сообщение от Mysterious Light Посмотреть сообщение
4. Отмечаем вершину как «достигнутую».
А можете дать совет, как в паскале это реализовать.

Цитата Сообщение от Mysterious Light Посмотреть сообщение
5. Ищем всех соседей для рассматриваемой вершины (строки).
Соседи - это вершины, в которые из рассматриваемой вершины исходят дуги?

Дальше идет совсем темный лес.
0
Mysterious Light
Эксперт по математике/физике
4094 / 2003 / 410
Регистрация: 19.07.2009
Сообщений: 3,022
Записей в блоге: 22
31.01.2013, 19:39 11
Цитата Сообщение от Lilu666 Посмотреть сообщение
Это как понять? Если нет единиц, то это как бы корень дерева получается?
Верно, я предлагаю на этом сыграть. Сразу можно определить вершину, которая потенциально может быть корнем. Если её нет — это уже не дерево. Если есть, от неё стартуем рекурсию.
Цитата Сообщение от Lilu666 Посмотреть сообщение
4. Отмечаем вершину как «достигнутую».
А можете дать совет, как в паскале это реализовать.
Следует создать дополнительный булевый массив (размер — число вершин), заполнить его false. Отмечаем вершину с номером i присваиванием true i-й ячейке. Если в i-й ячейке true — вершина отмечена, иначе false.
Цитата Сообщение от Lilu666 Посмотреть сообщение
Соседи - это вершины, в которые из рассматриваемой вершины исходят дуги?
Прочитайте подпункты. Идейно: пусть рассматривается вершина с номером i. Она инцидентна одной дуге со стороны входа (1) и нескольким дугам со стороны выхода (-1). Каждая выходящая дуга идёт к какой-то другой вершине, для которой она будет входящей. Они-то и обозначены как соседи. Для их поиска нужно сначала найти номера всех дуг, которые инцидентны вершине (подпункт i), затем для каждой из инцидентных дуг следует найти второй конец (подпункт ii).
Цитата Сообщение от Lilu666 Посмотреть сообщение
Дальше идет совсем темный лес.
Это не очень хорошо. Попробуйте для маленьких деревьев (3-5 вершин) пройтись таким образом, от корня к листкам. А потом добавьте к дереву лишнюю дугу, которая его портит, и посмотрите, что меняется в таком обходе.
Описанный алгоритм является не чем другим, как обходом дерева в глубину, начиная от корня. Если Вы знакомы с упомянутым DFS, то, думаю, сможете его реализовать.
1
darkenmark
8 / 8 / 2
Регистрация: 29.01.2013
Сообщений: 40
01.02.2013, 00:12 12
смотря что тебе именно нужно найти если просто узнать что инцидентность является графом то да если тебе нужно прогу написать то смотри алгаритм дейкстри, франкенсоль, гулиба и ширина и там все поймешь что тебе нужно
0
01.02.2013, 00:12
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.02.2013, 00:12

Создать бинарное дерево, по правой ветке - переменные типа инт, по левой - 2 переменные типа чар
Здравствуйте. Необходимо создать бинарное дерево, по правой ветке - переменные типа инт, по левой...

Создать коллекцию типа Граф
Помогите пожалуйста сделать или объясните как это сделать)) Создать собственную коллекцию типа...

Структура типа бинарное дерево на с++
здравствуйте, нужно спроектировать структуру типа бинарное дерево для использования в программах....


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
12
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru