Полный граф

Cтраница 2

Полный граф Кр, в котором любые две вершины смежны, может быть помечен только одним способом, и каждый его остов соответствует своему помеченному дереву. [16]

Рассмотрим полный граф с п вершинами ( который, очевидно, неплоский при п 5) и предположим, что некоторые его ребра окрашиваются в красный цвет, а оставшиеся ребра - в голубой. [17]

Критический граф, не являющийся реберно-критическим. [18]

Каждый полный граф критический. Действительно, для UcV ( KP) справедливо равенство % ( KP-U) p - U. Отсюда в свою очередь вытекает, что если и и v - любые две вершины n - критического неполного графа G, то существуют такая его п-рас-краска, что и и v принадлежат одному и тому же одноцветному классу, и такая его n - раскраска, что и и v принадлежат разным одноцветным классам. [19]

Каков наименьший полный граф, который при окраске его ребер в два цвета непременно порождает монохроматический полный граф с пятью вершинами. В 1975 г. Харари предложил премию в 100 долларов тому, кто первым найдет решение этой задачи, но премия до сих пор остается невостребованной. [20]

Подграфом полного графа называется любой граф, содержащийся в полном графе в том смысле, что все вершины и ребра подграфа принадлежат полному графу. Нетрудно видеть, что любой полный граф является подграфом любого полного графа с большим числом вершин. Многие простые графы имеют свои собственные названия. На рис. 108 представлены четыре семейства графов: маршруты, циклы, звезды и колеса. [21]

Для полного графа Kk i при нечетном k достигается верхняя оценка. [22]

Синтезированная структура схемы ( v 5. [23]

ДУЛ полного графа схемы с числом узлов п - f - 1, a г - - эмиттерный зажим 1-го необратимого элемента. [24]

Располагая полным графом альтернативных решений, построенным любым из двух указанных выше путем, можно весьма просто определить оптимальный типаж. [25]

В полном графе с двадцатью вершинами существует приблизительно 6 1 1016 гамильтоновых циклов, перечисление которых требует чрезвычайно много машинной памяти и времени. [26]

В полном графе всегда существует гамильтонов путь. [27]

В полном графе с п вершинами все ребра покрашены в три цвета. Доказать, что найдется одноцветный связный подграф, содержащий не менее л / 2 вершин. [28]

В полном графе каждая вершина одной части графа соединена с каждой вершиной другой части графа. [29]

Граф и его дополнение.| Наименьшие нетривиальные самодополнительные графы. [30]

Страницы: 1 2 3 4