67599

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

Лекция

Математика и математический анализ

Пусть утверждение верно для цикла длиной k-1. Допустим, в цикле имеются совпадающие вершины: vi=vj, (если их нет, то цикл - простой). Тогда удалим из цикла часть, заключенную между viи vj (вместе с vj). Получившийся цикл имеет меньшую длину и в силу индуктивного предположения из него можно выделить простой цикл.

Русский

2014-09-12

128 KB

9 чел.

Лекция 8

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

Пусть D=(V,X) орграф, V={v1,...,vn}, X={x1,...,xm}.

Матрицей смежности орграфа D называется квадратная матрица

A(D)=[aij] порядка n, где

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

Для неориентированных графов G=(V,X)

Матрицей смежности графа G называется квадратная симметричная матрица A(G)=[aij] порядка n, где

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

Примеры.

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

   

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

,  

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

       

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

Свойства матриц смежности и инцидентности.

Для ориентированного мультиграфа D=(V,X), V={v1,...,vn}, X={x1,...,xm}

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

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

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

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

Для неориентированного мультиграфа G=(V,X), V={v1,...,vn}, X={x1,...,xm}

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

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

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

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

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

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

опр || Последовательность

v1x1v2x2v3...xkvk+1, (где k1, viV, i=1,...,k+1, xjX, j=1,...,k)

в которой чередуются вершины и ребра (дуги) и для каждого j=1,...,k ребро (дуга) xj имеет вид {vj,vj+1} (для орграфа (vj,vj+1)), называется маршрутом, соединяющим вершины v1 и vk+1 (путем из v1 в vk+1).

Пример

v1x1v2x2v3x4v4x3v2 - маршрут,

x1x2x4x3 - маршрут можно восстановить и по этой записи,

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

v2x2v3x4v4 - подмаршрут.

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

Маршрут (путь) называется замкнутым, если начальная вершина совпадает с конечной v1=vk+1.

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

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

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

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

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

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

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

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

Пусть утверждение верно для цикла длиной k-1. Допустим, в цикле имеются совпадающие вершины: vi=vj, (если их нет, то цикл - простой). Тогда удалим из цикла часть, заключенную между viи vj (вместе с vj). Получившийся цикл имеет меньшую длину и в силу индуктивного предположения из него можно выделить простой цикл.

Теорема ||

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

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

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

1=v1x1v2...xk-1vk, 2=vkxkvk+1...xL-1vL называется путь (маршрут) 12=v1x1v2...xk-1vkxkvk+1xk+1...xL-1vL.


 

А также другие работы, которые могут Вас заинтересовать

51530. Определить горизонтальную составляющую индукции магнитного поля Земли 532.5 KB
  В этом случае к генератору подсоединяются последовательно только амперметр и магазин сопротивлений Rдоб. Установили на магазине сопротивлений какоелибо значение Rдоб например Rдоб = 3000 Ом и получите на экране осциллографа устойчивую картину изображенную на рис. Измерили величину =0 и определили разность фаз колебаний входного напряжения и напряжения на активном сопротивлении Rдоб φ=0 А=04 В. Δа=0049 кОм Rдоб=34 кОм ΔR=003 кОм χ2=356.
51531. ИЗУЧЕНИЕ ЗАКОНОВ ПЕРЕМЕННОГО ТОКА 3.44 MB
  При этом в цепи возникает переменный электрический ток. С помощью переключателя К катушка индуктивности может быть отключена от цепи. Замыкание кнопочного переключателя К4 приводит к отключению емкости от цепи. Для определения действующего значения силы тока в цепи используется вольтметр универсальный цифровой на котором должен быть установлен режим измерения силы переменного тока m.
51532. ИЗУЧЕНИЕ СЛОЖЕНИЯ ГАРМОНИЧЕСКИХ КОЛЕБАНИЙ С ПОМОЩЬЮ ОСЦИЛЛОГРАФА 2.12 MB
  Устройство и принцип работы электронного осциллографа рассмотрены в Приложении 1. Электронный осциллограф С1137 может работать в двух основных режимах: а Исследуемый сигнал подается на вход канала вертикального отклонения осциллографа вход I или II а на вход канала горизонтального отклонения подается пилообразное напряжение с генератора развертки встроенного в осциллограф. При этом на экране осциллографа наблюдается график зависимости исследуемого сигнала от времени.
51533. Определение длины электромагнитной волны по методу Лехера 72 KB
  Электромагнитные волны можно пролучить и в двухпроводной линии если ее подключить к высокочастотному источнику тока рис. При малой частоте генератора тока смещения можно пренебречь по сравнению с токами проводимости и в этом случае электромагнитные явления существенно зависят от сопротивлений линии т. Пусть в точке О двухпроводной линии рис. Электрическое поле будет распространяться вдоль линии и в произвольной точке D1 отстоящей от О на ростоянии х также возникнут гармонические колебания вектора .