Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.75/4: Рейтинг темы: голосов - 4, средняя оценка - 4.75
Dennis Ritchie
549 / 141 / 58
Регистрация: 27.07.2014
Сообщений: 2,446
1

Раскраска вершин графа

13.02.2015, 04:56. Просмотров 837. Ответов 10

Имеется такая задачка:
Раскраски (вершин графа) различны, если хотя бы одна вершина графа получает в этих раскрасках различный цвет. Сколько различных вершинных раскрасок графа P2 (цепи на двух вершинах) в цвета из множества 1,2,3,…,10?
1 22 33 44 55 66 77 88 99 10
1 32 43 54 65 76 87 98 10 
1 42 53 64 75 86 97 10  
1 52 63 74 85 96 10   
1 62 73 84 95 10    
1 72 83 94 10     
1 82 93 10      
1 92 10       
1 10        

У меня получилось 45. Но 45 не подходит. Что я не так сделал?
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.02.2015, 04:56
Ответы с готовыми решениями:

Раскраска графа
Условие и рисунок такие же как и на данном сайте http://domzadanie.ru/ans.php?id=155&show=all...

Раскраска графа
Граждане, подскажите, какой метод точной раскраски графа более оптимален для реализации на компе?...

Раскраска графа
Доброго времени суток! Как найти число рёбер графа при решении задачи "о раскраске" графов? ...

Раскраска планарного графа в 5 цветов
Собственно задача: раскрасить планарный граф в 5 цветов. Я поступаю следующим образом: используя...

Раскраска графа в минимальное количество цветов
Пишут, что это NP-полная задача, и якобы алгоритм последовательной раскраски при обходе в глубину...

10
SlavaSSU
218 / 163 / 47
Регистрация: 17.07.2012
Сообщений: 587
13.02.2015, 07:05 2
Лучший ответ Сообщение было отмечено Dennis Ritchie как решение

Решение

Dennis Ritchie, 1) почему нету раскрасок (1, 1), ... , (10, 10), это тоже раскраски же.

2)и еще раскраски (2, 1), ..., (10, 9), (10, 8), ... (10, 1) - тоже раскраски.

1) точно а вот 2) может быть и нет, но я так понял из условия, что вершины занумерованы, поэму раскраски (1, 2) и (2, 1) - различны.
1
Dennis Ritchie
549 / 141 / 58
Регистрация: 27.07.2014
Сообщений: 2,446
13.02.2015, 07:17  [ТС] 3
Цитата Сообщение от SlavaSSU Посмотреть сообщение
1) точно а вот
55 тоже не подходит.
Цитата Сообщение от SlavaSSU Посмотреть сообщение
2) может быть и нет
100 тоже не подходит.
0
SlavaSSU
218 / 163 / 47
Регистрация: 17.07.2012
Сообщений: 587
13.02.2015, 07:27 4
Dennis Ritchie, откуда задача?
0
13.02.2015, 07:27
Dennis Ritchie
549 / 141 / 58
Регистрация: 27.07.2014
Сообщений: 2,446
13.02.2015, 07:32  [ТС] 5
Цитата Сообщение от SlavaSSU Посмотреть сообщение
1) точно
Нет, наоборот, эти вершины брать не надо, потому что нужно найти только различные раскраски.
Цитата Сообщение от SlavaSSU Посмотреть сообщение
а вот 2) может быть и нет, но я так понял из условия, что вершины занумерованы, поэму раскраски (1, 2) и (2, 1) - различны.
А вот эти вершины нужно брать обязательно, поэтому правильный ответ 90.

Добавлено через 1 минуту
SlavaSSU, отсюда:
Демонстрационный урок 1 по дискретным структурам
0
SlavaSSU
218 / 163 / 47
Регистрация: 17.07.2012
Сообщений: 587
13.02.2015, 07:33 6
Dennis Ritchie, так что ответ 90? нигде не сказано, что нельзя красить вершины в одинаковый цыет.
0
Dennis Ritchie
549 / 141 / 58
Регистрация: 27.07.2014
Сообщений: 2,446
13.02.2015, 08:09  [ТС] 7
SlavaSSU, да, правильный ответ 90. На видео к демонстрационному курсу сказано.

Добавлено через 27 минут
Сколько различных рёберных раскрасок графа P3 (цепи на трёх вершинах) в цвета из множества 1,2,…,10?
У меня получилось 120 * 6 = 720, но ответ не подходит.

Добавлено через 3 минуты
Вот так я считал:
(36+28+21+15+10+6+3+1)*6=720

Добавлено через 3 минуты
Цифра 6 - количество перестановок из трёх чисел.
0
SlavaSSU
218 / 163 / 47
Регистрация: 17.07.2012
Сообщений: 587
13.02.2015, 09:10 8
Лучший ответ Сообщение было отмечено Dennis Ritchie как решение

Решение

Dennis Ritchie, попробуй 90.
1
Dennis Ritchie
549 / 141 / 58
Регистрация: 27.07.2014
Сообщений: 2,446
13.02.2015, 09:22  [ТС] 9
SlavaSSU, почему именно столько (это правильный ответ)? Что-то я переборщил.
0
SlavaSSU
218 / 163 / 47
Регистрация: 17.07.2012
Сообщений: 587
13.02.2015, 09:26 10
Dennis Ritchie, потому что надо красить ребра, а не вершины. у цепи на 3 вершинах 2 ребра.
ну и красим 2 ребра всеми способами, но чтобы одинаковых цветов не были они(прям как предыдущая задача, только красим 2 ребра, а не 2 вершины)
0
Dennis Ritchie
549 / 141 / 58
Регистрация: 27.07.2014
Сообщений: 2,446
13.02.2015, 09:29  [ТС] 11
Цитата Сообщение от SlavaSSU Посмотреть сообщение
потому что надо красить ребра, а не вершины. у цепи на 3 вершинах 2 ребра.
Да, я чего-то затупил. Подумал, что ребра тоже 3 (хотя знал, что их 2).
0
13.02.2015, 09:29
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.02.2015, 09:29

Число вершин связности графа
Помогите пожалуйста мне надо написать прогу по нахождению Числа вершин связности графа я уже...

Генетический алгоритм размещения вершин графа
Привет всем.Тут решение одной задачи. Кто может объясните откуда из p1 -1 2 3 4 5 взялось L1 = 3+...

Раскраска вершин графа
Как можно раскрасить вершины графа, используя минимальное количество красок, имея матрицу смежности...


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

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

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