Cтраница 2
Рассмотрим снова задачу подсчета всех неизоморфных обыкновенных графов, имеющих пять вершин. [16]
Доказать, что если ребра полного обыкновенного графа случайным образом ориентированы, то полученный ориентированный граф обязательно содержит ориентированное дерево, которое покрывает этот граф. [17]
В частности, внешне устойчивое множество для обыкновенного графа, который является р-однородным ( 6 ( и. [18]
Вторая импликация выражает прежнюю теорему Менгера для обыкновенного графа Lxy. [19]
Обыкновенный граф, полученный путем удаления ребер данного обыкновенного графа G из полного графа, имеющего т же самые вершины. [20]
Алгоритм отыскания путей между заданными вершинами в обыкновенном графе принадлежит С. [21]
Сначала заметим, что если теорема верна для обыкновенных графов, то она верна и для любых других графов. Будем поэтому считать, что граф является обыкновенным. Очевидно, что G не может быть ориентируемым, если существует ребро e - ( v&. [22]
Покажем теперь, что необходимое условие, при котором обыкновенный граф является плоским, состоит в том, чтобы граф можно было изобразить на плоскости с помощью прямых линий. Любой обыкновенный граф, плоский или нет, может быть изображен прямыми линиям ] в трехмерном пространстве. [23]
Покажем теперь, что необходимое условие, при котором обыкновенный граф является плоским, состоит в том, чтобы граф можно было изобразить на плоскости с помощью прямых линий. Любой обыкновенный граф, плоский или нет, может быть изображен прямыми линиям ] в трехмерном пространстве. [24]
Это наименьшее число называется хроматическим числом графа в соответствии с приведенной выше формулировкой задачи раскраски. Хроматическое число обыкновенного графа G, имеющего и вершин, меньше чем п, если G неполный, и больше 1 если ( 5 вообще содержит какие-нибудь ребра. [25]
Граф называется обыкновенным), если он не содержит петель и параллельных ребер. Заметим, что обыкновенный граф можно также определить как граф, не имеющий циклов, которые содержат менее трех ребер. Во многих случаях достаточно рассматривать только обыкновенные графы. Например, связность графа ( или отсутствие ее) не меняется, если удалить все петли и параллельные ребра. Аналогично, если каждому ребру графа приписана неотрицательная длина, то процедура поиска кратчайшего пути между некоторыми двумя вершинами не меняется, если удалить все петли и параллельные ребра, кроме кратчайших. [26]
При таких ограничениях не всякая сеть может быть отпечатана на двух сторонах платы. В главе 4 было показано, что обыкновенный граф G и его дополнения не являются плоскими графами, если G имеет девять или более вершин. Таким образом, полный ( обыкновенный); граф, имеющий девять вершин, нельзя отпечатать, на заданной плате, так как это означало бы, что некоторый подграф G ( часть сети, отпечатанная на одной стороне) и его дополнение ( часть, отпечатанная на другой стороне) являются плоскими. [27]
Ориентированный граф называется обыкновенным, если он не имеет строго параллельных дуг и петель. Заметим, что если обыкновенный ориентированный граф имеет параллельные, но противоположно ориентированные дуги, то соответствующий неориентированный граф уже не будет обыкновенным графом в неориентированном смысле, так: -; у он содержит параллельные ребра. [28]
Граф G ( X, U) называют расплывчатым, если для каждой вершины л: еХ множество LI является расплывчатым. Очевидно, что если и ( х) для любых х, z / eX принимает значения 0 или 1, то расплывчатый граф G становится обыкновенным графом. Для расплывчатого гиперграфа функция принадлежности определяется так же, как и для расплывчатого графа. [29]
Достаточно доказать лемму в предположении, что v не лежит на границе бесконечной грани, содержащей требуемую точку в бесконечности, так как с помощью сферической проекции можно сделать так, чтобы v лежала на границе внутренней грани. Каждая последовательная пара вершин Vi, Vt i лежит на границе треугольной грани, которая, следовательно, содержит третью вершину. С, что противоречит сказанному выше. Следовательно, треугольные грани, смежные с Cv включают общую вершину v, а так как G является обыкновенным графом, то Cv должен - совпадать с Cv и лемма доказана. [30]