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.


 

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

10147. Основные направления развития науки Нового времени. Научно-исследовательские программы Нового времени 46 KB
  Основные направления развития науки Нового времени. Научно-исследовательские программы Нового времени В XVII в. социокультурные основания обусловившие тенденции секуляризации познания и возрастания его индивидуального творческого характера углубляются. B экономичес...
10148. Направления развития и важнейшие результаты науки в ХVIII - XIX вв. Формирование дисциплинарной организации науки 30.5 KB
  Направления развития и важнейшие результаты науки в ХVIII XIX вв. Формирование дисциплинарной организации науки. Наука в своих развитых формах является дисциплинарноорганизованным знанием. Отдельные отрасли и научные дисциплины выступают как относительно автоном
10149. Методологические принципы и социально-организационные изменения науки в XVIII - XIX вв. Формирование науки как профессиональной деятельности 38.5 KB
  Методологические принципы и социально-организационные изменения науки в XVIII XIX вв. Формирование науки как профессиональной деятельности К наиболее примечательным методологическим разработкам того времени относятся: формирование эксперимента как базового метода эмп...
10150. Многообразие типов научного знания. Специфика естественных, гуманитарных и технических наук. 48 KB
  Многообразие типов научного знания. Специфика естественных гуманитарных и технических наук. Рассматривая познание как деятельность мы можем поставить следующую проблему. Можно ли утверждать что по аналогии с многими видами деятельности человека познавательна
10151. Соотношение эмпирического т теоретического уровней научного знания. Изменение представлений о взаимосвязи теории и эмпирии в философии науки ХХ в. 27.5 KB
  Соотношение эмпирического т теоретического уровней научного знания. Изменение представлений о взаимосвязи теории и эмпирии в философии науки ХХ в. Внутренняя структура науки определяется в п.о. через выделение в ее составе теоретического и эмпирического познания. Т.
10152. Формы систематизации знания на эмпирическом уровне 38.5 KB
  Формы систематизации знания на эмпирическом уровне. Основными методами эмпирического познания являются наблюдение и эксперимент. Наблюдение это целенаправленное восприятие явлений действительности в ходе которого фиксируются данные об их свойствах и отноше
10153. Наблюдение и эксперимент как эмпирические методы исследования, специфика их реализации в современной науке 34.5 KB
  Наблюдение и эксперимент как эмпирические методы исследования специфика их реализации в современной науке Общенаучные эмпирические методы. Наблюдение это преднамеренное целенаправленное и планомерное восприятие выделенного для изучения фрагмента реальности. Осо
10154. Научное знание: структура и методы теоретического знания. Абстрагирование и идеализация - начало теоретического познания 42 KB
  Научное знание: структура и методы теоретического знания. Абстрагирование и идеализация начало теоретического познания. Абстракции возникают на аналитической стадии исследования когда начинают рассматривать отдельные стороны свойства и элементы единого процесс...
10155. Научная картина мира как форма систематизации научного знания, ее виды и функции. 82.5 KB
  Научная картина мира как форма систематизации научного знания ее виды и функции. Как особый структурный феномен не входящий полностью в теоретическое знание в настоящее время выделяется еще научная картина мира. НКМ целостная система представлений об общих ...