Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.57/7: Рейтинг темы: голосов - 7, средняя оценка - 4.57
dandnm
0 / 0 / 0
Регистрация: 03.04.2013
Сообщений: 25
1

Алгоритмы на графах, формирование двудольного неориентированного графа

21.06.2013, 22:15. Просмотров 1233. Ответов 6
Метки нет (Все метки)

Пишу на c#, у нас есть множество вершин графа, хранящихся в List<V>
Множество ребер хранится в двух вариантах: в виде матрицы весов(двумерный массив), и в виде списка списков т.е.

типа list<list<E(V1,V2)>> (список смежностей). (Можно использовать любой вариант хранения который удобен для алгоритма)

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

Помогите пожалуйста реализовать этот алгоритм на C#, хотя можно и на С++.

Добавлено через 9 минут
И формирование должно происходить с помощью добавления ребер
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.06.2013, 22:15
Ответы с готовыми решениями:

Алгоритмы на графах
Поиск минимального остовного дерева как-то связан с поиском кратчайших путей между вершинами ?

Алгоритмы на графах
Привет всем, мне нужна помощь з алгоритмами на графах нашел алгоритм Дейсктры // oo.cpp : Defines...

Алгоритм поиска циклов неориентированного графа
Помогите пожалуйста. Нужен алгоритм, который считал бы циклы неориентированного графа.

Задача определения двудольного графа
2.3.7 Задача определения двудольного графа. Граф называется двудольным, если можно разбить...

Найти кратчайшее расстояние из вершины v1 неориентированного взвешенного графа в другие вершины графа
Пользуясь алгоритмом Дейкстры, найти кратчайшее расстояние из вершины v1 неориентированного...

6
Mysterious Light
Эксперт по математике/физике
4082 / 1995 / 405
Регистрация: 19.07.2009
Сообщений: 3,012
Записей в блоге: 21
22.06.2013, 01:03 2
Дан граф. Нужно добавить в него рёбра, чтоб он стал двудольным. Я правильно понял?

Ребра двудольного графа соединяют вершины разных (двух) цветов. Две вершины одного цвета несмежны.
Мне кажется, что любой недвудольный граф сделать двудольным добавлением ребер не получится.
Например, полный граф уже не двудольный.
Другой пример. Звезда — это двудольный граф. Добавьте хотя бы одно ребро к нему. Сколько бы к этому графу не добавляйте, никогда двудольный не получите.
0
dandnm
0 / 0 / 0
Регистрация: 03.04.2013
Сообщений: 25
22.06.2013, 17:45  [ТС] 3
а ну значит еще и удаление разрешается)
0
Igor3D
1227 / 594 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
22.06.2013, 18:00 4
Нужен код на С++ или словесное описание?
0
dandnm
0 / 0 / 0
Регистрация: 03.04.2013
Сообщений: 25
23.06.2013, 12:08  [ТС] 5
Нужен код или словесное описание

Желательно код, если к нему будет словесное описание то еще лучше. Если только словесное описание, то спасибо и на этом
0
Igor3D
1227 / 594 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
23.06.2013, 12:27 6
Каждая вершина имеет поле "цвет", одно из 3 значений
-1 = не установлен
0 = красный
1 = синий

Изначально всем вершинам присваиваем цвет -1. Создаем пустой список вершин.

1) Если список пуст - находим первую вершину с цветом -1, меняем это цвет на 0 и помещаем в список. Если нет вершин с цветом -1, то все сделано

2) Извлекаем вершину из списка и в цикле смотрим цвет смежных вершин (по ребрам)
- если цвет смежной вершины == самой, то удаляем ребро
- если противоположный 0/1, то ничего не делаем
- если -1, то присваиваем противоположный и помещаем ее в список
До тех пор пока список не пуст. Потом переход к п 1
1
dandnm
0 / 0 / 0
Регистрация: 03.04.2013
Сообщений: 25
23.06.2013, 14:24  [ТС] 7
Спасибо)
0
23.06.2013, 14:24
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.06.2013, 14:24

K-связность неориентированного графа
Ребят, третью неделю уже думаю, не могу решить. Нужно написать программу на с++, определяющую...

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

Программа обработки неориентированного графа
Она должна проверять наличие в графе хотя бы одного цикла


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

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

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