Математический аппарат инженера | страница 34
4. Типы конечных графов.Если множество вершин графа конечно, то он называется конечным графом. В математике рассматриваются и бесконечные графы, но мы заниматься ими не будем, так как в практических приложениях они встречаются редко. Конечный граф G = (V, E), содержащий р вершин и q ребер, называется (р, q)-графом.
Рис. 9. Типы графов:
а - псевдограф; б - полный граф (шестиугольник); в - двудольный граф (биграф).
Пусть V = { v>1, v>2, ..., v>p } и E = { e>1, e>2, ..., e>q } - соответственно множества вершин и ребер (р, q)-графа. Каждое ребро e>k ∈ E соединяет пару вершин v>i ∈ V являющихся его концами (граничными вершинами). Для ориентированного ребра (дуги) различают начальную вершину, из которой дуга исходит, и конечную вершину, в которую дуга заходит. Ребро, граничными вершинами которого является одна и та же вершина, называется петлей. Ребра с одинаковыми граничными вершинами являются параллельными и называются кратными. В общем случае граф может содержать и изолированные вершины, которые не являются концами ребер и не связаны ни между собой, ни с другими вершинами. Например, для (5, 6)-графа на рис. 9, а V={ v>1, v>2, v>3, v>4, v>5 }; Е= {e>1, e>2, e>3, e>4, e>5} ребра e>2 и e>3 параллельны, ребро e>6 является петлей, а v>4 - изолированная вершина.
- 48 -
Число ребер, связанных с вершиной v>i (петля учитывается дважды), называют степенью вершины и обозначают через δ(v>i) или deg (v>i). Так, для графа на рис. 9, а δ(v>1) =1, δ(v>2) = 4 и т. д. Очевидно, степень изолированной вершины равна нулю δ(v>4) = 0). Вершина степени единицы называется концевой или висячей вершиной ( δ(v>1) =1). Легко показать, что в любом графе сумма степеней всех вершин равна удвоенному числу ребер, а число вершин нечетной степени всегда четно. В орграфе различают положительные δ>+(v>i) и отрицательные δ>-(v>i) степени вершин, которые равны соответственно числу исходящих из v>i и заходящих в v>i дуг. Например, для вершины d орграфа (см. рис. 9, а) имеем δ>+(d) = 2 и δ>-(d) = 3. Очевидно, суммы положительных и отрицательных степеней всех вершин орграфа равны между собой и равны также числу всех дуг.
Граф без петель и кратных ребер называют простым или обыкновенным. Граф без петель, но с кратными ребрами называют мультиграфом. Наиболее общий случай графа, когда допускаются петли и кратные ребра, называют псевдографом. Так, граф на рис. 7,б - это мультиграф, а на рис. 9, а - псевдограф. Если граф не имеет ребер (Е = ∅), то все его вершины изолированы (V ≠ ∅), и он называется пустым или нульграфом. Простой граф, в котором любые две вершины соединены ребром, называется полным (на рис. 9, б приведен пример полного графа с шестью вершинами). Если множество вершин V простого графа допускает такое разбиение на два непересекающихся подмножества V
