Пример. Основные понятия и определения

Пример.

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

Элементы теории графов

Во многих прикладных задачах изучаются системы связей между различными объектами. Математической моделью, позволяющей решать подобные задачи, является граф.

Определение. Графом называется система G =(V, E), где

V ={ v ₁, v ₂, …, v_n } – непустое множество вершин графа,

E ={{ v_i, v_j } | v_i, v_j Î V для некоторых i, j Î{1, …, n }} – множество ребер графа.

1) Сеть улиц в городе: вершины – перекрестки, ребра – улицы;

2) блок-схемы программ: блоки – вершины, ребра – переходы от одного блока к другому;

3) электрические цепи;

4) молекулы химических соединений;

5) социальные связи.

Ребра вида { v_i, v_i } называются петлями. Одинаковые элементы множества E называются кратными (параллельными) ребрами. Число вхождений пары вершин { v_i, v_j } в множество E называется кратностью соответствующего ребра.

Замечание. Иногда для графа с петлями и кратными ребрами используют термин псевдограф, псевдограф без петель называют мультиграфом, а под собственно графом понимают мультиграф, все ребра которого имеют кратность, равную единице.

Если ребра графа задаются упорядоченными парами вершин, то граф называется ориентированным (орграфом). Ребра орграфа называют дугами. Таким образом, если G =(V, E) – орграф, то E ={(v_i, v_j) | v_i, v_j Î V для некоторых i, j Î{1, …, n }}, т.е. E Í V ².

Соответствующую графу G геометрическую конфигурацию, в которой вершины изображены кружочками, а ребра ­– линиями, соединяющими соответствующие вершины, будем называть изображением этого графа. Направления дуг в орграфе отмечаются стрелками на соответствующих линиях.

Если e ={ v_i, v_j } – ребро графа G, то v_i, v_j называются концами ребра e, и говорят, что e соединяет вершины v_i, v_j. Если e =(v_i, v_j) – дуга орграфа G, то v_i называется началом, а v_j – концом дуги e, и говорят, что e исходит из вершины v_i и заходит в v_j.

Если вершина v является концом (началом или концом) ребра (дуги) e, то говорят, что v и e инцидентны. Два ребра, имеющие общую вершину, называются смежными. Две вершины смежны, если в графе есть соединяющее их ребро.

Степенью вершины v называется число ребер, инцидентных этой вершине. Обозначается deg v.

Вершина, степень которой равна 0, называется изолированной, а вершина со степенью 1 называется висячей.

Полустепенью исхода (захода) вершины v называется число дуг, исходящих из вершины (заходящих в вершину). Обозначается deg^– v (deg⁺ v).

Замечание. Если G – неориентированный псевдограф, то вклад каждой петли, инцидентной вершине v, в deg v равен 2. Если G – ориентированный псевдограф, то вклад каждой петли, инцидентной v, равен 1 как в deg^– v, так и в deg⁺ v.

Дата добавления: 2014-01-04