Форум программистов, компьютерный форум, киберфорум
C# для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.70/30: Рейтинг темы: голосов - 30, средняя оценка - 4.70
0 / 0 / 0
Регистрация: 10.12.2012
Сообщений: 80
1

Найти хроматическое число графа: нужен алгоритм или пример

27.12.2012, 00:19. Показов 6040. Ответов 1
Метки нет (Все метки)

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

Алгоритм сжатия PPM - нужен пример
Доброго времени суток.. Ребята, у кого есть реализованный алгоритм сжатия pрm на С++/С# поделитесь...

Хроматическое число графа
Здравствуйте =) Не можете подсказать какой-либо алгоритм нахождения хроматического числа графа

Хроматическое число графа
Есть какой-то алгоритм для поиска хроматического числа графа (наименьшее возможное число цветов в...

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

1
1055 / 862 / 195
Регистрация: 31.03.2010
Сообщений: 2,521
27.12.2012, 13:35 2
Вики

По-моему тут можно решить только полным перебором.
1. Разбиваем множество вершин на все возможные минимальные покрытия(то есть чтоб одна вершина не входила в разные подмножества)
Кликните здесь для просмотра всего текста

(123)
1,2,3
(1,2), 3
(1,3),2

(1234)
1,2,3,4
(1,2), 3,4
(1,2), (3,4)
(1,3), 2, 4
(1,3), (2,4)
(1,4), 2,3
(1,4), (2,3)
(1,2,3), 4
(1,2,4), 3
(1,3,4),2
(2,3,4),1

Каждое подмножество вершин это вершины одного цвета.
2.1 проходим по всем покрытиям
2.2 проходим по подмножествам покрытия
2.3. Для каждой пары вершин подмножества проверяем если ли среди них такие, что соеденены ребром.
если такая пара встречается, то исключаем данное покрытие.
3. Среди тех покрытий, что остались находим покрытие с наименьшим количеством подмножеств. Количество множеств такого покрытия и будет решением.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
27.12.2012, 13:35

Нужен пример построения графа
Помогите,пожалуйста.Нужен пример построения графа на windows forms.Обшарил весь интернет и ничего...

Найти хроматическое число простой цепи, состоящей из 9 вершин
Хроматическое число простой цепи состоящей из 9 вершин равно... Варианты: 2 , 3 , 4 ,5. ...

Алгоритм Дейкстры, привести пример взвешенного графа
Привести пример взвешенного графа на 5 вершинах, на котором в процессе работы алгоритма Дейкстры ни...

Нужен алгоритм поиска пути в этом лабиринте (будь то волновой алгоритм или алгоритм правой/левой руки )
#include "stdafx.h" #include <iostream> #include <conio.h> using namespace std; void lab...


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

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

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