Определения. Геометрическая реализация графов

Маршруты, цепи, циклы

Геометрическая реализация графов

Фигура F называется геометрической реализацией графа G(V,E), если существует взаимно однозначное соответствие между точками фигуры F и вершинами графа, между кривыми фигуры и ребрами, такое, что соответствующие кривые и ребра соединяют соответствующие точки и вершины.

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

Теорема: каждый конечный граф допускает правильную укладку в трехмерном пространстве.

Граф называет планарным, если он допускает правильную укладку на плоскости.

Теорема (доказано в топологии): граф планарен, если он не имеет подграфов, изоморфных графам K₅ и K_3,3.

Маршрутом в графе G(V,E) называется чередующаяся последовательность вершин и ребер v₁, e₁, v₂, e₂,...,v_k,e_k,v_k+1, в которой любые два соседних элемента инцидентны.

Это определение подходит также для псевдо-, мульти- и орграфов. Для «обычного» графа достаточно указать только последовательность вершин или только последовательность ребер.

Если v₁=v_k+1, то маршрут замкнут, иначе открыт.

Если все ребра различны, то маршрут называется цепью. Если все вершины цепи различны, то цепь называется простой.

Замкнутая цепь называется циклом; замкнутая простая цепь называется простым циклом.

Число циклов в графе G обозначается z(G) (является инвариантом). Граф без циклов называется ациклическим.

Для орграфов цепь называется путем, а цикл - контуром.

Пример

В графе, диаграмма которого приведена на рис. 3.10:

1. v₁,v₃,v₁,v₄ - маршрут, но не цепь;

2. v₁, v₃, v₅, v₂, v₃, v₄ - цепь, но не простая цепь;

3. v₁, v₄, v₃, v₂, v₅ - простая цепь;

4. v₁, v₃, v₅, v₂, v₃, v₄, v₁- цикл, но не простой цикл;

5. v₁,v₃,v₄ - простой цикл.

Рис. 3.10. Маршруты, цепи, циклы

Две вершины графа называются связанными, если существует маршрут, соединяющий эти вершины. Граф называется связным, если любая пара его вершин связанна.

Граф называется деревом, если он связен и не содержит циклов.