Определения. Маршрутом в графе G(V,E) называется чередующаяся последовательность вершин и ребер v1, e1, v2, e2,

Маршрутом в графе 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. Маршруты, цепи, циклы

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

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

Поиск по сайту: