Главная /
Графы и их применение /
Какой граф G называется реберно k-раскрашиваемым?
Какой граф G
называется реберно k
-раскрашиваемым?
вопрос
Правильный ответ:
граф
G
называется реберно k
-раскрашиваемым, если его ребра можно раскрасить k
-красками таким образом, что никакие два смежных ребра не окажутся одного цвета
граф
G
называется реберно k
-раскрашиваемым, если его можно задать парой V(G),E(G)
, где V(G)
- непустое конечное множество элементов, называемых вершинами, а - E(G)
конечное семейство неупорядоченных пар элементов из V(G)
(не обязательно различных), называемых ребрами. Употребление слова "семейство" говорит о том, что допускаются кратные ребра. Будем называть V(G)
множеством вершин, а V(G)
- семейством ребер графа G
. О каждом ребре вида {v,w}
говорят, что оно соединяет вершины v
и w
. Каждая петля {v,v}
соединяет вершину v
саму с собой
граф
G
называется реберно k
- раскрашиваемым, если его можно задать бесконечным D(V(D),A(D))
графом D
, где V(D)
, непустое конечное множество элементов, называемых вершинами, а A(D)
- конечное семейство упорядоченных пар элементов из V(D)
, называемых дугами (или ориентированными ребрами). Дуга, у которой вершина v
является первым элементом, а вершина w
- вторым, называется дугой из v
в w(v,w)
. Заметим, что дуги (v,w)
и (w,v)
различны. Хотя графы и орграфы – существенно различные объекты, в определенных случаях графы можно рассматривать как орграфы, в которых каждому ребру соответствуют две противоположно ориентированные дуги
допустим, что множество вершин графа можно разбить на два непересекающихся подмножества
V1
и V2
так, что каждое ребро в G
соединяет какую-нибудь вершину из V1
с какой-либо вершиной из V2
, тогда граф G
называется реберно k
-раскрашиваемым Сложность вопроса
75
Сложность курса: Графы и их применение
81
Оценить вопрос
Комментарии:
Аноним
Это очень простой решебник по интуиту.
26 июл 2019
Аноним
Спасибо за решебник по intuit.
16 окт 2015
Другие ответы на вопросы из темы алгоритмы и дискретные структуры интуит.
- # Чему равна сумма чисел, стоящих в любой из строк матрицы инциденций графа G?
- # Можно ли получить двудольный граф соединением двух графов Km,n=Nm+Nn?
- # Можно получить несколько различных матриц смежности данного графа?
- # Что называется лесом?
- # Сколько несцепленных треугольников с одноцветными сторонами найдется в полном графе с восемью вершинами, ребра которого окрашены в два цвета?