Главная / Графы и их применение / Какой граф G называется k-раскрашиваемым?

Какой граф G называется k-раскрашиваемым?

вопрос

Правильный ответ:

если его ребра можно раскрасить k красками таким образом, что никакие два смежных ребра не окажутся одного цвета
если его можно задать парой (V(G), E(G)), где V(G) - непустое конечное множество элементов, называемых вершинами, а E(G) - конечное семейство неупорядоченных пар элементов из V(G) (необязательно различных), называемых ребрами. Употребление слова "семейство" говорит о том, что допускаются кратные ребра. Будем называть V(G) множеством вершин, а E(G) - семейством ребер графа G. О каждом ребре вида {v,w} говорят, что оно соединяет вершины v и w. Каждая петля (v,v) соединяет вершину v саму с собой
если его можно задать бесконечным графом D(V(D),A(D)), где V(D) непустое конечное множество элементов, называемых вершинами, а A(D) - конечное семейство упорядоченных пар элементов из V(D), называемых дугами (или ориентированными ребрами). Дуга, у которой вершина v является первым элементом, а вершина w - вторым, называется дугой из v в w(v,w). Заметим, что дуги (v,w) и (w,v) различны. Хотя графы и орграфы – различные объекты, в определенных случаях графы можно рассматривать как орграфы, в которых каждому ребру соответствуют две противоположно ориентированные дуги
пусть граф G не имеет петель; тогда G называется k-раскрашиваемым, если каждой его вершине можно приписать один из k цветов таким образом, чтобы никакие две смежные вершины не оказались одного цвета
Сложность вопроса
83
Сложность курса: Графы и их применение
81
Оценить вопрос
Очень сложно
Сложно
Средне
Легко
Очень легко
Комментарии:
Аноним
Спасибо за ответы интуит
26 мар 2018
Аноним
Экзамен сдан на зачёт.
20 сен 2016
Аноним
Спасибо за гдз по интуит.
31 янв 2016
Оставить комментарий
Другие ответы на вопросы из темы алгоритмы и дискретные структуры интуит.