Cтраница 2
Граф, состоящий из пустых списков вершин и дуг, называется пустым, а граф из одной вершины и без дуг - тривиальным. Набор базисных операций позволяет создать пустой граф и содержит базисные операции для работы с любым его списком. [16]
Ряд графов простой структуры заслуживает, как нам кажется, специальных названий. Для некоторых целей полезно ввести в рассмотрение нуль-граф ( или пустой граф), который не имеет ни ребер, ни вершин. Граф-петля состоит из единственной петли и ее одного конца ( рис. I. [17]
Поскольку при этом число вершин остается неизменным, неизменным будет оставаться и цикломатическое число. Но оно равно нулю, поскольку таким путем мы в конце концов приходим к пустому графу, цикломатическое число которого заведомо равно нулю. Из сказанного следует, что 7i ( L) 0 тогда и только тогда, когда граф L не содержит цикловых ребер, а значит ( по теореме 1), и циклов. [18]
Пустой граф определяется как граф, который не содержит ни вершин, ни ребер. [19]
Если G П Н Л ( в том случае, когда X П У 0), то говорят, что G и Н не пересекаются или G и Н - непересекающиеся графы. Подчеркнем, что пересечение существует у любых двух графов, в том числе и у непересекающихся, только у непересекающихся графов оно равно пустому графу. [20]
Легко видеть, что данный алгоритм должен завершиться. Также достаточно ясно, что перед началом каждого прохождения основного цикла все вершины от первой до ( текущаявершина - /) имеют допустимую раскраску. Чуть менее очевидно, что старшийцвет увеличивается только тогда, когда невозможно раскрасить некий начальный подграф выделенным числом цветов. Заметьте, что алгоритм правильно работает для пустого графа, для графов, все вершины которых изолированы, и для графов, все вершины которых связаны. [21]