1.10. Некоторые специальные классы графов

Графы можно классифицировать различными способами, в зависимости от структурных признаков, которые используются в качестве основы для классификации. Мы уже видели, что графы можно разбить на связные и несвязные, на плоские и неплоские и т. д. Введем теперь еще ряд полезных классификаций.

Граф называется обыкновенным, если он не содержит петель и параллельных ребер. Заметим, что обыкновенный граф можно также определить как граф, не имеющий циклов, которые содержат менее трех ребер. Во многих случаях достаточно рассматривать только обыкновенные графы. Например, связность графа (или отсутствие ее) не меняется, если удалить все петли и параллельные ребра. Аналогично, если каждому ребру графа приписана неотрицательная длина, то процедура поиска кратчайшего пути между некоторыми двумя вершинами не меняется, если удалить все петли и параллельные ребра, кроме кратчайших.

Граф называется полным, если любые две различные вершины являются смежными, т. е. соединяются ребром. Обычно этот термин применяется к обыкновенным графам. Для таких графов существует только один полный граф с фиксированным числом вершин, все остальные будут ему изоморфны. Следовательно, выражение «полный граф с вершинами» однозначно определяет граф. На рис. 1.3 изображен полный графе пятью вершинами.

Граф называется двудольным, если его вершины могут быть разбиты на два непересекающихся подмножества и так, что каждое ребро имеет одну граничную точку в а другую в В общем случае граф называется -дольным, если множество его вершин можно разбить на непересекающихся подмножеств так, что не существует ребер, соединяющих вершины одного и того же подмножества. Чтобы подчеркнуть отмеченную особенность двудольного графа, его часто изображают, размещая множества вершин и в разных столбцах (или строках), как. показано на рис. 1.11.

Граф называется -связным, если любая пара различных вершин соединена, по крайней мере, цепями, которые не имеют общих вершин, исключая, конечно, Например, любой простой цикл (исключая петли) образует -связный граф. При это понятие совпадает с понятием обычной связности.

Если для всех вершин графа, то граф называется однородным графом степени или просто k-однородным.

Рис. 1.11.

Рис. 1.12.

Например, на рис. 1.12 изображено несколько связных -однородных графов. Заметим, что обыкновенный полный граф, имеющий вершин, является -однородиым. Можно еще отметить, что согласно теореме 1.3 - однородный граф имеет четное число вершин, если нечетно.

Упражнения

(см. скан)

1.27. Приведите несколько примеров прикладных задач, в которых рассматриваемые графы являются двудольными по самой физике задачи. Такие графы, как правило, характерны для случаев, когда вершимы изображают объекты двух различных типов, а ребра служат для описания отношении между разнородными объектами, например, люди — работы, или посетители театра — номера занимаемых мест.

Замечание. На предыдущих страницах читатель мог заметить появление ряда понятий, связанных с идеей оптимальности. Напомним некоторые из них: простая цепь есть минимальное множество ребер, связывающее две заданные вершины. Покрывающее дерево есть максимальный подграф связного графа, который не содержит циклов, и минимальный подграф, который соединяет все вершины. Простои разрез есть минимальное множество ребер, удаление которых делает связный граф несвязным. Простой цикл является минимальным связным графом. Во всех этих понятиях минимальность (максимальность) означает, что не существует собственного подмножества (надмножества), или подграфа (над-графа), которое обладает тем же свойством.

Развитию этих идей уделено много внимания на последующих страницах как при введении дополнительных понятий, связанных с оптимальностью, так и при составлении упражнений. Будут рассмотрены задачи, связанные с нахождением кратчайших и длиннейших путей, максимальных потоков в сетях, потоков минимальной стоимости, разбиения множества вершин на наименьшее число его независимых подмножеств и т. д. Читателю рекомендуется обратить внимание на различные проявления идей оптимальности в последующих главах.

(см. скан)

ЛИТЕРАТУРА

(см. скан)

(см. скан)