Какой граф G называется реберно - Ответ на вопрос по любому предмету №1179070

Вопрос

• граф 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-раскрашиваемым

Ответ