Лекции 14. Основные понятия теории графов. Некоторые виды графов (4 часа)

Обозначения и определения
V – множество точек – вершины;
X – множество линий – ребра;
Графом называется совокупность множеств вершин и ребер.
v - номер вершины;
{v,w} – обозначение ребра;
{v,v} – петли;
Одинаковые пары - параллельные или кратные ребра;
Кратностью ребер называют количество одинаковых пар.
Пример. кратность = 3.
2. Мультиграф. Псевдограф. Полный граф.
Если в графе есть петли и/или кратные ребра, то такой граф называют псевдографом.
Псевдограф без петель называется мультиграфом.
Мультиграф в котором ни одна пара не встречается более одного раза называется графом.
Если пары (v,w) являются упорядоченными, граф называется ориентированным (орграфом).
Ребра ориентированного графа называются дугами.
В неориентированном графе ребра обозначаются неупорядоченной парой - {v,w}.
В ориентированном графе дуги обозначаются упорядоченной парой - (v,w).
G, G₀ - неориентированный граф, D, D₀ – ориентированный.
Обозначают v,w - вершины, x,y,z – дуги и ребра.
Пример
1) V={v₁, v₂, v₃, v₄},
X={x₁=(v₁,v₂), x₂=(v₁,v₂), x₃=(v₂,v₂), x₄=(v₂,v₃)}.



изолированная
вершина













висячая
вершина

2) V={v₁, v₂, v₃, v₄, v₅},

X={x₁={v₁,v₂}, x₂={v₂,v₃}, x₃={v₂,v₄}, x₄={v₃,v₄}}.