Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Графы

Автор: KIDD 29.4.2004, 11:36

Товарищи, есть у кого алгоритм доказательства двудольности графа на основе матрицы смежности, или может подскажите где это найти?

Спасибо

Автор: achmed 6.5.2004, 16:25

ну наверное надо посмотреть на определение и немного подумать ....

Шаг 1
Все вершины помечаем синим цветом.
Выбираем произвольную вершину v графа G,
помечаем ее красным цветом
Шаг 2
Ищем синюю вершину, не смежную ни одной красной вершине.
Если таковая находится, то красим ее в красный цвет повторяем, Шаг 2,
иначе переход в Шаг 3.
Шаг 3
если синих вершин не осталось, то граф двудольный (можно произвольно разбить мн-во красных вершин на две часи),
иначе,
проверяем мн-во синих вершин на смежность, если есть хоть одна пара смежных синих
вершин, то граф не двудольный, если нет, то граф двудольный.

Вот. Надеюсь понятно как эдесь используется матрица смежности

. Вместо покраски
можно использовать стек.

Интересно увидеть другие варианты, быть может более оптимальные.

Автор: njn 13.5.2004, 09:10

Подскажите, мошт глупый вопрос конечно, но все таки: Как с помошью алгоритма поиска в ширину доказать что граф двудольный.
Всем
Сенк

Автор: Фумска 3.6.2004, 12:23

Люди!!! Помогите пожалуйста!!!
Нужно срочно решить три задачи на Паскале, а я не знаю как:
1. перебор из 0 и 1
2. Написать программу, проверяющую связность графа
3. Построить дерево кратчайших путей (из заданной вершины) в графе
Заранее всем спасибо... вы очень меня выручите...

Автор: Blacksnow 4.8.2004, 10:05

Перебор 0-1 векторов.
Способы:
1. Сложение
2. Коды Грея (на каждом шаге меняеться только одна компонента)
3. Цепной код
Алгоритмы:
1. берешь нулевой вектор длины n и прибавляешь 1 на каждом шаге, пока не получиться единичный. Пример:
000
001
010
011
100
101
110
111
2. в основе лежит следуящая рекурсия: зафиксируем нулевое значение m компоненты, переберем все вектора длины m-1, и сменим значение m компоненты на 1. Пример:
0000
0001
0011
0010
0110
0111
0101
0100
1100
1101
1111
1110
1011
1001
1000
3. строиться 0-1 вектор длины 2^n, затем все 0-1 вектора длины n получаються циклическим сдвигом из построенного. Пример для n=4:
0111101011001000
0011110101100100
0001111010110010
0000111101011001.
***
В каком виде представлен граф?
***
Дерево кратчайших путей строиться по алгоритму Дейкстры, Беллмана-Форда и Левита.
Описывать алгоритмы долго, поищи в инете.

Автор: Тиньков 9.8.2004, 08:59

KIDD, njn
Проводим поиск в ширину, причём для каждой вершины запоминаем шаг, на котором она была этим поиском охвачена. Если нет ни одной пары смежных вершин с одинаковым значением шага, то граф - двудольный.

Фумска
2. Проводим поиск в ширину (или можно в глубину), помечая каждую охваченную вершину. Если останутся непомеченные - значит, граф несвязный.
3. Опять же поиск в ширину

) из заданной вершины, для каждой охваченной вершины запоминаем номер шага (т.е. расстояние до неё). Чтобы потом найти кратчайший путь из любой вершины, переходим из неё в любую соседку, имеющую меньший номер, до тех пор, пока не придём в начальную.