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.


 

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

54150. Анализ кредиторской задолженности 211 KB
  Эффективное управление кредиторской задолженностью предприятия на сегодняшний день является одной из первоочередных и актуальных задач для решения которых требуется провести исследования в этой области.
54151. ТИЖДЕНЬ МАТЕМАТИКИ 80 KB
  Шановні студенти Ми зібралися тут не тільки зясувати хто краще уміє вирішувати задачі головоломки рахувати а ще і для того щоб довідатися багато нового цікавого. Завдання вікторини написані на окремих аркушах кожний з яких містить малюнок Шановні студенти Дозвольте запропонувати вам невелику логічну задачу. Шановні студенти Чи не можете ви пояснити причину настільки дивного на перший погляд рішення математика Шановні студенти Відомо що всі тіла на Місяці в 6 разів менше ніж на Землі. Яке устаткування ви візьмете із...
54153. КОНКУРС ВЕСЕЛЫХ МАТЕМАТИКОВ 32.5 KB
  Сколько лыжников посещают хор Найдите пятую степень числа 2. Сколько денег досталось каждому Разделить на две части 25 рублей так чтобы одна часть была в 49 раз больше другой. Сколько лет человеку Если к возрасту моего сына прибавить столько и еще полстолько то получится 10 лет. Сколько лет сыну Сколько в 1 кубическом метре кубических сантиметров Исполняются номера художественной самодеятельности.
54154. «Математика - жизнь и здоровье человека» для учащихся 5-7 классов 83.5 KB
  Так как преподавание в школе ведётся на русском языке, с целью формирования и развития навыков общения на государственном языке сценарий разработан в виде диалога его участников на двух языках.
54155. Гра «Щасливий випадок» 51.5 KB
  Запитання для першої команди Результат додавання чисел називається сума Одиницею вимірювання площі є см Фігура яка складається з чотирьох точок і чотирьох відрізків що послідовно їх сполучають називається чотирикутник Площа квадрата обчислюється за формулою а Градусна міра прямого кута. 90˚ Прямі називаються паралельними якщо вони не перетинаються Рівність що містить змінну називається рівнянням Добуток всіх дійсних чисел дорівнює 0 Відрізок що зєднує вершину трикутника з серединою...
54156. Математичний бій 50 KB
  Хід заходу Ведучий 1: Добрий день всім хто зібрався сьогодні в цьому залі Ведучий 2: Всім шанувальникам великої і прекрасної науки. Ведучий 1: Математика. Ведучий 2: Математика. Ведучий 1: Математика це мистецтво наук і наука мистецтв Ведучий 2: Математика це політ фантазії і творчості.
54158. Математика в оточуючому світі 33.5 KB
  Відстань між пристанями А і В дорівнює 40 км. Від А до В за течією річки рухається моторний човен, власна швидкість якого 18 км/год., а від В до А – інший моторний човен, власна швидкість якого 16 км/год. При зустрічі виявилось, що перший човен йшов 1 год., а другий – 1,5 год. Знайдіть швидкість течії річки.