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.


 

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

36942. Оволодіти навиками створення програм, частини яких написані різними мовами програмування. Засвоїти правила взаємодії різних модулів 169.07 KB
  Звичайно доступ наприклад до двох параметрів переданих через стек здійснюється в такий спосіб: PUSH EBP MOV EBPESP MOV EX[EBP8] MOV EDX[EBP12] . POP EBP RET Деякі версії мови C розрізняють великі і малі букви тому ім'я асемблерного модуля повинне бути представлено в тому ж символьному регістрі який використовують для посилання Cпрограми.code _clc proc push ebp mov ebpesp mov ex[ebp16] shr ex01 mov ebx[ebp8] shl ebx02 sub ebxex sub ebx[ebp12] sub ebx[ebp8] mov ex[ebp20] dd exebx pop ebp ret _clc endp END ...
36943. Робота з масивами в СКМ Mathcad 24.73 KB
  Дано дві матриці А та В.7150 Транспонувати матриці А В С.1600 Знайти найменший елемент 3го стовпчику матриці С.1600 Вивести стовбець матриці С який містить максимальний елемент у виді окремого вектору.
36944. Побудова вибіркової функції розподілу засобами комп’ютерних технологій 363.5 KB
  Лабораторна робота №2 Тема: побудова вибіркової функції розподілу засобами комп’ютерних технологій. У MthCD існують дві функції що дозволяють зробити обробку вибірки для наступної побудови гістограм. Оскільки методика створення гістограм з використанням функції hist досить складна надамо її по пунктах: Для початку представимо експериментальні дані у вигляді вектора.
36945. Розрахувати найбільшу похибку відлікового пристрою і встановити раціональну точність виготовлення елементів багатооборотного індикатора 543.84 KB
  1 Функції перетворення синусного механізму: Для кулісного механізму Передаточне відношення від веденої ланкистрілки до кінцевої ланки кулісного механізму Вихідна функція з кулісного механізму враховуючи що вихід синусного є входом кулісного.
36946. Обладнання та драйвери. Використання Device Manager та System Information 316.54 KB
  Вивести властивості пристрою 1. Вивести список драйверів що забезпечують роботу даного пристрою відобразити у звіті рис. Імітуючи несправність пристрою неправильно під’єднаний шлейф SCSIпристрою запустити програму Troubleshooter Діагностика 1. Також я знайшов IRQ ресурси певних пристроїв та визначив які драйвера потрібні для роботи дискового пристрою відображені на рис2.
36947. Використання вбудованих функцій MathCAD, MS Exсel для обчислення характеристик вибірки 61.5 KB
  Для обчислення числових характеристик вибірки що утримується в масиві Х розмірності m×n в MthCD призначені наступні функції: mxХ – для пошуку найбільшого елемента в масиві даних; minХ – пошук мінімального елемента в масиві даних; sortХ – побудова варіаційного ряду тобто сортування вихідних даних по зростанню; menХ – обчислення вибіркового середнього по масиву даних: vrХ – для визначення вибіркової дисперсії; stdevХ – для обчислення середньоквадратичного відхилення; medin – для розрахунку значення медіани –...
36948. Мова програмування Matlab / Simulink 20.48 KB
  Скласти программу-функцію Matlab/Simulink для розв’язання задачі обробки одновимірного масиву у загальному вигляді, а обчислення на комп’ютері виконати для конкретних даних згідно з варіантом. Cформувати масив W з елементів масиву V, що задовольняють умову
36949. Використання засобів MathCAD, MS Excel для формування послідовностей випадкових чисел 56 KB
  Київ – 2011 Лабораторна робота №4 Тема: Використання засобів MthCD MS Exсel для формування послідовностей випадкових чисел. Мета: ознайомитися з основними видами розподілів випадкових чисел основними інструментами що використовуються при формування послідовностей випадкових чисел розглянути реалізацію методів формування цих послідовностей за допомогою різних інструментальних засобів MthCD Excel. Теоретична довідка У табличному процесорі Excel для формування послідовності випадкових чисел використовується...
36950. Побудова графіків в Matlab / Simulink 233.79 KB
  Висновок: під час лабораторної роботи я вивчив графічні можливості СКМ Matlab/Simulink.