§ 35. p-цветный граф. Граф с p отображениями. Неориентированный мультиграф, или неориентированный p-граф

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

Рис. 147.

Рис. 148.

Рис. 149.

p-цветный граф. Пусть заданы графов

Рис. 150.

Рис. 151.

Объединим их на одном чертеже и, взяв цветов, окрасим дуги каждого из каким-либо одним цветом. То, что получится, называют -цветным графом и обозначают через

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

Например, объединяя графы на рис. 147—149 в один, получаем -цветный граф, изображенный на рис. 150.

Понятие -цветного графа не имеет, конечно, ничего общего с понятием неориентированного -хроматического графа.

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

Рис. 152.

Например, если в -цветном графе на рис. 150 не обращать внимания на цвета, то его можно рассматривать как граф с отображениями (рис. 151), но легко привести пример -цветного графа, который таким же путем приводит к графу с отображениями, где

Каждому -цветному графу можно сопоставить (неоднозначно из-за произвольной нумерации дуг) граф с отображениями, где обратно, каждому графу с отображениями можно сопоставить (неоднозначно из-за произвольного выбора цвета дуг) -цветный граф, где

Понятие графа с отображениями используется в теории связи, теории автоматов и т. д.

Граф с одним отображением представляет собой граф в смысле теории множеств.

Мультиграф, или p-граф. Другое обобщение касается неориентированных графов. В качестве вершин рассматриваются элементы некоторого конечного множества и предполагается, что различные вершины могут быть соединены несколькими ребрами. Если максимум числа ребер, соединяющих две вершины, равен то говорят о неориентированном мультиграфе порядка или -графе. Например, на рис. 152 изображен -граф.

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