Cтраница 3
В полном графе Кр каждая пара его р вершин 2) смежна. [31]
Может ли полный граф иметь 7 8 9 или 10 ребер. [32]
Поскольку каждый новый полный граф вносит в полиэдрическую систему точно одну новую скелетную связывающую орби-таль, каждое применение полиэдрического дырообразования требует для получения стабильной системы добавления двух электронов. [33]
Поскольку каждый полный граф КР для р 3 содержит простой цикл, граф G не может быть одним из этих графов. Граф G должен быть связным, так как в ином случае можно было бы добавить ребро х, соединяющее две вершины из разных компонент графа G, и граф G д: был бы ациклическим. [34]
Теорема 3.22. Антисимметрический полный граф G содержит единственный гамильтонов путь тогда и только тогда, когда он не содержит контуров. [35]
Каждая вершина полного графа Кп соединена с любой другой его вершиной. [36]
Матрица смежности полного графа Кп имеет п строк и п столбцов. На главной ее диагонали ( пересечение строк со столбцами того же номера) стоит Л, а вне ее - И. [37]
Очевидно, что полный граф всегда содержит гамильто-нов цикл. Начальную вершину называют корнем, из которого выходят ребра, называемые ветвями дерева. Очевидно, что в дереве любые две вершины xi, Xj дерева связаны единственной цепью. Для задач конструирования РЭА наибольший интерес представляют деревья, у которых число вершин равно числу вершин графа, из которого выделено это дерево. Такие деревья называют покрывающими. [38]
По лемме 7 полный граф / Cft с множеством вершин В; разлагается на ( k - l) / 2 остовных циклов. [39]
Пусть Gn обозначает полный граф из п вершин. Требуется определить / минимальное число пересечений ребер, когда Gn изображен на плоскости так, что в любой точке, отличной от вершин, пересекается не более двух ребер. [40]
Теорема 2.23. Каждый полный граф с шестью вершинами и минимальным числом пересечений изоморфен графу, изображенному на фиг. [41]
Если теперь рассмотреть гипотетический полный граф О с п вершипами и взять в качестве длины ребра ( х &, х ]) максимальный поток / у между соответствующими вершинами яг и X) из С, то эти длины можно использовать для построения длиннейшего остова Т графа С, применяя один из методов построения кратчайшего ( или длиннейшего) остова, приведенных в гл. [42]
Заметим, что полный граф Gn содержит как эйлеровы, так и гамильтоновы циклы. Задачи выделения эйлеровых и гамильтоновых циклов тесно связаны с так называемыми задачами о лабиринте и о коммивояжере. Задача о лабиринте в терминах теории графов формулируется как задача определения в связном графе G ( X, U) такого маршрута S, который начинается в заданной вершине Xi и приводит в другую искомую вершину Xj, причем маршрут S должен содержать кратчайшее число ребер. Известные методы Тэрри, Трюмо, Люка и Кенига, описанные в работе О. Оре [115], позволяют находить такой маршрут. [43]
Матрицей А задается ориентированный полный граф без петель и встречных дуг, такой граф часто называют турниром ( или круговым турниром), так как он может отображать результаты спортивных состязаний, где все команды ( или спортсмены) встречаются друг с другом один раз, причем результатом каждой встречи может быть только выигрыш или поражение. Сумма элементов i - й строки итоговой таблицы турнира равна количеству побед, одержанных i - й командой. [44]
Заметим, что обыкновенный полный граф, имеющий k вершин, является ( k - 1) - однородным. Можно еще отметить, что согласно теореме 1.3 - однородный граф имеет четное число вершин, если k нечетно. [45]