Найдите вероятность того, что жадное хроматическое число графа на 4 вершинах и 3 ребрах равно 2.

Жадный алгоритм раскраски графа заключается в следующем: Пусть зафиксировано множество вершин 𝑉 = {1, 2, ..., 𝑛}. Жадный алгоритм работает следующим образом. Вершине 1 по определению присваивается цвет 1. Каждая следующая вершина из списка вершин красится в цвет с минимальным номером такой, что с предыдущими вершинами нет конфликта по цветам ни по каким ребрам.

Жадное хроматическое число - это количество цветов, которое получено в результате работы такого жадного алгоритма.

задан 26 Июн '19 17:43

изменен 26 Июн '19 17:44

@worker: если я правильно понял условие, то ответ зависит от того, какой именно граф рассматривается (их всего три с точностью до изоморфизма), а вероятность берётся для случайной разметки вершин. Если так, то всё находится прямым перебором. Для треугольника + точка х.ч. равно 3, и "жадное" всегда такое же. Для "трилистника" (одна вершина соединена с тремя) любая "жадная" раскраска даёт ответ 2. Остаётся случай линейного графа (цепи). Здесь вершина 1 с вероятностью 1/2 крайняя или не крайняя. Во втором случае ответ всегда "2". В первом вероятность ответа "3" равна 1/2; итого ответ 3/4.

(26 Июн '19 19:32) falcao

@falcao, я исхожу из того, что для графа на 4 вершинах и 3 ребрах справедливо равенство: жадное хроматическое число равно 2 тогда и только тогда, когда граф либо дерево, не являющееся простым путем на вершинах (звезда), либо его вершины занумерованы определенным образом. Т.е. у нас есть 4 звезды + простые пути на 4-х вершинах, занумерованные определенным образом. Общее это число потом нужно поделить на C(C(4,2),3) = C(10,3) = 20. Теперь простые пути, занумерованные определенным образом -> жад.хром.чис. = 3, только для нумераций (1,3,4,2); (1,4,3,2); (1,2,4,3).

(26 Июн '19 19:47) worker

@falcao, способов построить путь на 4 вершинах 4!/2 (известная формула). Т.е. получаем: (4+(4!/2)-3)/20 = 13/20

(26 Июн '19 19:50) worker

@falcao, здесь сложность, как мне кажется, крылась в том, чтобы увидеть, что для простых путей только три нумерации вершин дают жад.хром.число 3...

(26 Июн '19 19:52) worker

@worker: если сам граф на 4 вершинах случаен, а номера вершин даны сразу, то это будет совсем другая задача. Тогда её надо правильно ставить. Возможен вариант, когда мы сначала выбираем одно ребро из 6 и проводим, потом одно из пяти, потом одно из четырёх. Тогда учитываются вероятности появления того или другого графа. Такая формулировка мне нравится больше, но в текущей версии условия она не нашла отражения -- даже если именно она подразумевалась.

(26 Июн '19 20:28) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,462
×624

задан
26 Июн '19 17:43

показан
735 раз

обновлен
26 Июн '19 20:28

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru