Обыкновенный граф

Cтраница 1

Обыкновенный граф, полученный путем удаления ребер данного обыкновенного графа G из полного графа, имеющего т же самые вершины. [1]

Рассмотрим обыкновенный граф с п вершинами. Дополнительный граф получается, если из полного ( обыкновенного) графа с п вершинами вычеркнуть все ребра, содержащиеся в исходном графе. Граф является само-дополнительным, если он изоморфен своим дополнением. Так, например, граф на рис. 4.9 самодополнительный. [2]

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

В обыкновенном графе G вершина и доминирует над собой и над б ( и) вершинами, с которыми она смежна. [4]

Если U - обыкновенный граф, то по индуктивному предположению существует прямолинейный граф S, изоморфный G. Теперь нужно доказать, что вершина v, соответствующая и, может быть выбрана таким образом, чтобы ее можно было связать отрезками прямых с требуемыми вершинами, не пересекая при этом другие отрезки. Рассмотрим цикл Cv ( v, v2, , vkv i) графа S, соответствующий С в лемме 4.13, где v, в S соответствует и в G. [5]

Даны топологические представления связанных плоских обыкновенных графов ГА и ГБ. [6]

На рис. 1.1 изображен обыкновенный граф. Обыкновенные графы можно задавать более просто, а именно в виде двух множеств X и U, где X - множество вершин, a U - некоторое множество неупорядоченных различных пар вершин. [7]

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

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

Предлагаются алгоритмы реализации преобразования связанных плоских обыкновенных графов, которые были разработаны для синтеза автоматов в четырехнаправленных универсальных вычислительных однородных структурах. [10]

Двойственный граф был бы полным обыкновенным графом из пяти вершин, который не является плоским. [11]

Некоторые виды графов. а обыкновенный граф. б связный граф с петлей. в обыкновенный ориентированный граф - дерево. [12]

Определение 6.2. Если G - обыкновенный граф, в котором имеется п узлов и п - 1 связей и отсутствуют циклы, то такой граф является деревом. [13]

Применив теорему о раскраске ребер обыкновенного графа [1], получим следующее утверждение. [14]

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

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