Матрицы смежности и инцидентности

Размещено на http://www.allbest.ru/

Лекция

Матрицы смежности и инцидентности

Пусть D=(V,X) орграф.

V={v₁,...,v_n}, или X={x₁,...,x_m}.

Матрицей смежности орграфа D называется квадратная матрица A=[a_ij] порядка n, где:

Матрицей инцидентности называется матрица B=[b_ij] порядка nm, где:

Для неориентированных графов G=(V,X). Матрицей смежности графа G называется квадратная симметричная матрица A(G)=[a_ij] порядка n, где:

Матрицей инцидентности графа G называется матрица B(G)=[b_ij] порядка nm, где:

Примеры.

1. Для орграфа, изображенного на рис.

2. Для графа, изображенного на рис.

Ориентированный псевдограф.

С помощью этих матриц графы задаются на ЭВМ.

Свойства матриц смежности и инцидентности. Для ориентированного мультиграфа D=(V,X), V={v₁,...,v_n}, X={x₁,...,x_m}

- сумма строк матрицы B(D) является нулевой строкой (дуга один раз входит и один раз выходит);

- любая строка матрицы B(D) является линейной комбинацией остальных строк (вследствие предыдущего);

- ранг матрицы B(D) не превосходит n(D)-1 (также вследствие предыдущего);

- для любого контура в D сумма столбцов матрицы B(D), соответствующих дугам, входящим в этот контур, равна нулевому столбцу.

Для неориентированного мультиграфа G=(V,X), V={v₁,...,v_n}, X={x₁,...,x_m}.

- сумма строк матрицы B(G) по модулю 2 является нулевой строкой (дуга один раз входит и один раз выходит, а вместе четно);

- любая строка матрицы B(G) является суммой по модулю 2 остальных строк (вследствие предыдущего);

- для любого цикла в G сумма по модулю 2 столбцов матрицы B(G), соответствующих ребрам, входящим в этот цикл, равна нулевому столбцу.

Определение. Матрица C=[c_ij], у которой c_ij={0,1} наз. булевой.

Если G - псевдограф без кратных ребер, матрица смежности - булева.

Маршруты и пути.

Последовательность:

- в которой чередуются вершины и ребра (дуги) и для каждого j=1,...,k ребро (дуга) x_j имеет вид {v_j,v_j+1} (для орграфа (v_j,v_j+1)), называется маршрутом, соединяющим вершины v₁ и v_k+1 (путем из v₁ в v_k+1).

Пример:

v₁, x₁, v₂, x₂, v₃, x₄, v₄, x₃, v₂ - маршрут,

x₁, x₂, x₄, x₃ - маршрут можно восстановить и по этой записи,

v₁, v₂, v₃, v₄, v₂ - если кратности ребер (дуг) равны 1, то можно и так.

v₂, x₂, v₃, x₄, v₄ - подмаршрут.

Число ребер в маршруте называется длиной маршрута (пути).

Маршрут (путь) называется замкнутым, если начальная вершина совпадает с конечной:

v₁ = v_k + 1

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

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

Замкнутый маршрут (путь), в котором все ребра (дуги) попарно различны, называется циклом (контуром).

Цикл (контур), в котором все вершины попарно различны называется простым.

Теорема. В псевдографе G (в ориентированном псевдографе D) из всякого цикла (контура) можно выделить простой цикл (простой контур).

Доказательство (индукцией).

Пусть k - количество ребер, k+1 - количество вершин в цикле (или контуре).

При k=1 (петля) цикл всегда является простым.

Пусть утверждение верно для цикла длиной k-1.

Допустим, в цикле имеются совпадающие вершины: v_i=v_j, (если их нет, то цикл - простой).

Тогда удалим из цикла часть, заключенную между v_iи v_j (вместе с v_j). Получившийся цикл имеет меньшую длину и в силу индуктивного предположения из него можно выделить простой цикл.

Теорема. матрица мультиграф теорема

Из всякого незамкнутого маршрута (пути) можно выделить простую цепь с теми же начальной и конечной вершинами.

Доказательство аналогично предыдущему.

Определение. Композицией путей (маршрутов)

₁ = v₁, x₁, v₂, x_k-1, v_k.

₂ = v_k, x_k, v_k+1, x_L-1, v_L - называется путь (маршрут).

Размещено на Allbest.ru