Способы задания графов
Графы принято изображать рисунками, состоящими из точек, называемыми вершинами, и линий, называемыми дугами, соединяющими две вершины графа.
Форма дуг несущественна, важен только сам факт соединения вершин. Дуги могут пересекаться, но точки пересечения не являются вершинами графа.
Если дуги имеют направление (ориентацию), отмеченное стрелкой, то такие графы называются ориентированными или орграфами. Дуги графа часто называют ребрами.
Вершины графа будем обозначать v
, а дуги x. На рис.3.1 изображен граф, а на рис.3.2 – орграф.
|
|
||
Рис3.1 Рис.3.2
Дуга в орграфе, имеющая направление от вершины v к вершине vј , назы-вается
выходящейиз вершины vi и заходящейв вершину vj. При этом
вершина vi называется началом дуги, а
vj – ее концом.
Дуги, соединяющие две одинаковые вершины не ориентированного графа, называются кратными. На рис.3.1 это дуги x1 и x2.
Дуга, выходящая из вершины и входящая в нее, называется петлей. На рис.3.2 это дуга x4.
Дуги орграфа называются параллельными, если они соединяют две одинаковые вершины
графа и имеют одно направление. На рис.3.2 это дуги x
и
x
.
Дуги орграфа называются противоположными, если они соединяют две одинаковые вершины графа и противоположно направленны. На рис.3.2 это дуги x1
и x2.
Две вершины графа называются смежными, если они соединены дугой, иначе они называются несмежными.
Вершина графа (орграфа) называется изолированной, если она не соединяется дугой с
другими вершинами графа. На рис.3.1 это вершина v.
Граф с кратными дугами и петлями называется псевдографом. Ориентированный псевдограф соответственно имеет параллельные дуги и петли. Орграф на рис.3.2 является ориентированным псевдографом.
предыдущая темаследующая