0 / 0 / 0
Регистрация: 28.07.2012
Сообщений: 8
1

Выбрать минимальное количество вершин в двудольном неориентированном графе

11.12.2017, 06:45. Показов 1095. Ответов 3
Метки нет (Все метки)

У нас есть двудольный неориентированный граф. Нужно выбрать минимальное количество вершин так, чтобы на концах ребер, ведущих из данных вершин, распологалась каждая вершина графа. Подскажите, пожалуйста, с чего начать.
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
11.12.2017, 06:45
Ответы с готовыми решениями:

В заданном неориентированном графе найти все Гамильтоновы пути, соединяющие указанную пару вершин
Здравствуйте. Задание: в заданном неориентированном графе найти все гамильтоновы пути, соединяющие...

Количество мостов в неориентированном графе
Здравствуйте, я хотел бы посчитать количество мостов,с помощью нахождения компонент реберной...

Посчитать количество компонент связности в неориентированном графе
В неориентированном графе посчитать количество компонент связности. В графе могут быть петли и...

В неориентированном графе посчитать количество компонент связности
2. Компоненты связности В неориентированном графе посчитать количество компонент связности. В...

3
Диссидент
Эксперт C
26970 / 16845 / 3705
Регистрация: 24.12.2010
Сообщений: 37,821
11.12.2017, 10:40 2
Если каждая из "долей" состоит более чем из одной вершины, то достаточно взять по вершине из каждой "доли".
Если же какая-то доля состоит из одной вершины, достаточно взять эту вершину.
0
0 / 0 / 0
Регистрация: 28.07.2012
Сообщений: 8
11.12.2017, 14:14  [ТС] 3
Спасибо за ответ. Эксплицитно не было дано, но граф необязательно полный двудольный. У графа ниже выбрать две вершинины из разных долей так, чтобы выполнялось условие не получится.
Выбрать минимальное количество вершин в двудольном неориентированном графе
0
Диссидент
Эксперт C
26970 / 16845 / 3705
Регистрация: 24.12.2010
Сообщений: 37,821
11.12.2017, 19:16 4
Цитата Сообщение от Alerks Посмотреть сообщение
но граф необязательно полный двудольный.
Понял. Прошу прощения. Сбила с толку картинка в вики.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
11.12.2017, 19:16
Помогаю со студенческими работами здесь

Поиск вершины с максимальной степенью в двудольном графе
Здравствуйте, имеется двудольный граф (X, Y). X - это пары целых чисел Y - это просто целые...

Перевод из Delphi (Алгоритм нахождения наибольшего паросочетания в двудольном графе)
UNIT1 unit Unit1; interface uses Windows, Messages, SysUtils, Variants, Classes,...

Минимальное количество ребер в графе
Дано n вершин и m ребер в неориентированном графе. Далее идет по два числа - вершины ребер. Вывести...

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


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru