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.


 

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

4581. Управление затратами предприятия на примере ООО «Кормилец» 184.81 KB
  Дать характеристику и классификацию издержек обращения в торговых предприятиях; изучить методы управления затратами; дать характеристику деятельности ООО «Кормилец»; сделать анализ финансового состояния предприятия; разработать план мероприятия по управлению затратами; дать оценку эффективности данных мероприятий...
4582. Сучасні технології захисту інформації в комп’ютерних системах і мережах 2.15 MB
  Частина друга присвячена питанням захисту інформації в комп’ютерних мережах. До її складу входять роботи: Перехоплення мережевого обміну, Сканування TCP/IP мереж, Засоби аналізу захищеності, Міжмережеві екрани, Системи виявлення атак. Лаборатор...
4583. Використання методу Монте-Карло для вирішення стохастичних і детермінованих задач 80 KB
  Використання методу Монте-Карло для вирішення стохастичних і детермінованих задач. Мета роботи:Ознайомитись з методом статистичних випробувань (метод Монте-Карло), та його застосуванням для вирішення стохастичних та детермінованих задач. Метод...
4584. Знайомство з системою комп’ютерної математики - математичною матричною лабораторією MATLAB 232.5 KB
  Знайомство з системою комп’ютерної математики - математичною матричною лабораторією MATLAB. Мета роботи: Ознайомитися з основними елементами і складовими частинами системи комп’ютерної математики MatLab® і її робочим і програмним середовищ...
4585. Планування модельних експериментів. Стратегічне планування модельного експерименту 101 KB
  Планування модельних експериментів. Стратегічне планування модельного експерименту. Мета роботи: Ознайомитися з методами стратегічного планування імітаційних експериментів. Планування модельних експериментів Припустимо, три юні натураліст...
4586. Методи управління модельним часом: моделювання з постійним кроком і по особливих станах 101 KB
  Методи управління модельним часом: моделювання з постійним кроком і по особливих станах. Мета роботи: Вивчити методи управління модельним часом. Ознайомитися і програмно реалізувати алгоритми управління модельним часом з постійним кроком і по особли...
4587. Субтрактивне змішування кольорів. Диск Максвелла 38.52 KB
  Субтрактивне змішування кольорів. Диск Максвелла. Виконання роботи. Визначення координат ахроматичної точки. Підібрали такі розміри зовнішніх секторів з кольорами Cyan, Magenta, Yellow, що їх суміш дала ахроматичний колір. Отримали наступні коорд...
4588. Розрахунок припусків на механічну обробку оптичних деталей 47 KB
  Розрахунок припусків на механічну обробку оптичних деталей Мета роботи: Ознайомити студентів з методикою розрахунків припусків на розміри оптичних поверхонь деталей при їх обробці в оптичному виробництві. Завдання 1. Ознайомитись з видами припусків ...
4589. Інсталювання та налагодження мережевих компонент однорангової мережі Windows 9x. 103 KB
  Інсталювання та налагодження мережевих компонент однорангової мережі Windows 9x, Робота в одноранговій мережі. Керування доступом на рівні ресурсів. Використання спільних каталогів та мережевого принтера. Методичні вказівки з курсу Операційні ...