logo search
Лекции_по_ДМ

Основные определения теории графов

Граф – математический объект, описываемый двумя множествами: G=V), где V – так называемое множество вершин, а Eмножество дуг.

Элементами множества дуг являются упорядоченные пары вершин, т.е. E={ ( ab): aVbV }, т.о. множество Е является подмножеством декартова произведения VV. Порядок вершин в парах может и не учитываться, тогда элементы множества Е называют ребрами, а сам граф – неориентированным графом, в противном случае – ориентированным или Орграфом. В некоторых случаях рассматриваются так называемые смешанные графы, в них множество Е состоит из элементов обоих видов: дуг и ребер.

Обозначим вершины v1, v2, v3, , а ребра e1, e2, e3, . Вершины vi и vj, определяющие ребро ek, называются концевыми вершинами ребра ek=(vivj), а в случае орграфа – началом и концом дуги ek соответственно. Говорят также, что ребро ek (дуга) инцидентно вершинам vivj или, что вершины vivj инцидентны ребру (дуге) ek. Такие вершины называют смежными. Ребра называют смежными в случае, когда они имеют общую концевую вершину. Например, ek=(vivj) и em=(vivl) – смежные ребра.

В множестве ребер графа допускается более, чем одно ребро с одинаковыми концевыми вершинами. Такие ребра называются параллельными или кратными. Например: ek=(vivj) и em=(vivj) – кратные ребра.

Если обе концевые вершины ребра совпадают, то такое ребро называется петлей. Например: ek=(vivi) – петля.

Граф без петель и параллельных ребер называется простым, в противном случае – мультиграфом.

Граф, не имеющий ребер, называется пустым, а не имеющий вершин (а значит и ребер) – нуль‑графом.

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

Количество вершин в графе называется порядком графа.

Степенью или валентностью вершины называется число инцидентных ей ребер. Будем обозначать степень вершины vi – deg(vi). Вершина нулевой степени называется изолированной. Вершина степени 1 называется висячей, а ребро, инцидентное ей, называется висячим ребром. Заметим, что петля добавляет двойку к степени вершины.