Меню
Главная
Авторизация/Регистрация
 
Главная arrow Математика, химия, физика arrow ГЕОМЕТРИЧЕСКАЯ ТЕОРИЯ ГРАФОВ
Посмотреть оригинал

Мультиграфы и псевдографы

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

Однородные графы

Граф называется однородным {регулярным) степени к, если все его вершины имеют одинаковую степень к. Однородный граф нулевой степени называется нуль-графом или пустым графом. Он не имеет ребер и состоит только из изолированных вершин. Однородный граф третьей степени называется кубическим графом. В силу теоремы 1, любой однородный граф нечетной степени (в частности, любой кубический граф) содержит четное число вершин. Полный граф с п вершинами является однородным степени п-1, а полный граф с петлями - однородным степени п+1.

Двудольные и к-дольные графы

Конечный мультиграф называется двудольным или бихроматическим, если его вершины могут быть разделены на два непересекающихся подмножества V/ и V2 так, что каждое ребро имеет одну граничную точку в V), а другую в V2. Т.е. любое ребро графа не может соединять вершины из одного подмножества. Чтобы подчеркнуть это свойство двудольных графов, их обычно изображают, размещая множества вершин V/ и V2 в разных столбцах или строках ( см. пример двудольного графа на рис. 18).

Двудольный граф называется элементарным, если он не содержит параллельных ребер (на рис. 18 пред- V, ставлен элементарный двудольный граф).

Элементарный двудоль- р ^

ный граф называется

полным, если любая пара вершин из разных подмножеств соединена ребром (см. рис. 1). Полный двудольный граф содержит |Zs| = |V, | • |V2| ребер.

Аналогично определяется k-дольный граф при к > 2. Это такой мультиграф, вершины которого можно разделить на к непересекающихся подмножеств так, чтобы ребра не соединяли вершины из одного подмножества. Любой мультиграф с п вершинами можно рассматривать как и-дольный граф. Каждая его «доля» состоит всего из одной вершины. В частности, полный граф с п вершинами является n-дольным графом и не является ^-дольным графом для к < п.

 
Посмотреть оригинал
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 

Популярные страницы