Однородный граф

Cтраница 1

Однородный граф - это граф, у которого все вершины имеют одинаковую степень. [1]

Теорема 7.5.1. Однородный граф не имеет дефицита. [2]

Теорема 7.5.3. Почти однородный граф G, в котором отклонения, определяемые в (7.5.6), удовлетворяют условиям (7.5.8), имеет однородный суграф первой степени. [3]

Если О - однородный граф, то он восстанавливаем. [4]

Наибольшую трудоемкость представляет установление изоморфизма однородных графов, имеющих автоморфные подграфы. Для решения таких задач используются методы разбиения исследуемых графов на различные уровни. [5]

На рис. 1.2.2 приведены примеры двух бесконечных однородных графов. [6]

Требование, чтобы граф имел заданную группу, не налагает существенных ограничений на другие его свойства. Избицкий и Сабидусси показали, что можно найти однородный граф с произвольными степенью, связностью, хроматическим числом и другими характеристиками. [7]

Заметим, что обыкновенный полный граф, имеющий k вершин, является ( k - 1) - однородным. Можно еще отметить, что согласно теореме 1.3 - однородный граф имеет четное число вершин, если k нечетно. [8]

Графики зависимости условной ЦФ от числа итераций.| График зависимости времени решения от числа итераций. [9]

Задача распознавания изоморфизма графов является одной из важнейших комбинаторно-логических задач. Проблема определения изоморфизма двух графов, расположенных на плоскости, заключается в получении одного графа из другого путем перенумерации их вершин. Другими словами, необходимо найти подстановку множество вершин, переводящую один граф в другой. Как отмечалось выше, наибольшую трудность при определении изоморфизма представляют однородные графы. Было случайно сгенерировано сто однородных графов, а затем в этих же графах выполнена случайная перестановка их вершин. Следовательно, заранее было известно, что анализируются изоморфные графы, в которых нужно определить подстановку, переводящую один граф в другой. В таблице 7.6 в столбце 2 приведено количество вершин исследуемых графов. В столбце 3 указаны локальные степени вершин графов. [10]

Страницы: 1