Введение в информационные системы. Брюхомицкий Ю.А. - 59 стр.

UptoLike

Составители:

Рубрика:

Рис. 5.3. Пример графа, содержащего параллельные ребра, петлю

и изолированную вершину

Граф без петель и кратных ребер называют простым или обыкновен-

ным. Граф без петель, но с кратными ребрами называют мультиграфом. Наибо-

лее общий случай графа, когда допускаются петли и кратные ребра, называют

псевдографом. Так, граф, показанный на

рис. 5.3, является псевдографом. Если

граф не имеет ребер (Е = ), то все его вершины изолированы (V  ), и он

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

шины соединены ребром, называется полным графом, рис. 5.4.

Рис. 5.4. Полный граф (шестиугольник)

Если множество вершин V

простого графа допускает такое разбиение

на два непересекающихся подмножества V

и V

 V

= ), что не сущест-

вует ребер, соединяющих вершины одного и того же подмножества, то он назы-

вается двудольным или биграфом, рис. 5.5.

Рис. 5.5. Двудольный граф (биграф)

Орграф считается простым, если он не имеет строго параллельных дуг

и петель.