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.


 

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

80933. Структура та методичне забезпечення підручника «Всесвітньої історії» (10-11кл.) 37.68 KB
  Бесіда діалогічний метод навчання за допомогою якого вчитель із поставленими питаннямь спонукає учнів відтворювати раніше набуті знання робити самостійні висновкиузагальнення на основі засвоєного фактичного матеріалу. Бесіда є одним із активних методів навчання. Бесіда дозволяє залучити до діяльності на уроці дітей незалежно від їхнього рівня підготовки та індивідуальних можливостей що сприяє досягненню високих результатів у навчально виховному процесі. Така бесіда зазвичай проводиться на початку вивчення теми чи розділу.
80934. Аналіз програми з історії України для 5 кл. Мета ,завдання та зміст 29.92 KB
  Головною метою курсу є підготовка учнів до успішного опанування систематичних курсів історії України та всесвітньої історії прищеплення інтересу до історії отримання знань у наступних класах через формування в них початкових уявлень про історію як науку та про історію України як складову світової історії елементарних вмінь з історії; поглиблення загальних дидактичних вмінь необхідних для успішного засвоєння історичної інформації в подальшому; прагнення викликати захоплення минулим України. Зміст курсу ґрунтується на таких засадах:...
80935. Кабінет історії в школі, його значення 34.32 KB
  Важливе значення має вигляд меблів якими обладнаний кабінет. Важливе значення має також оформлення передньої стінки яку складають державна символіка України розкладна проста чи магнітна дошка екран шафи з тумбами стаціонарний стелаж чи рухома підставка для книг.
80936. Аналіз програми з історії України для 6-9 кл. Мета ,завдання та зміст 35.39 KB
  Мета завдання та зміст. Програма з історії спрямована на реалізацію вимог освітньої галузі Суспільствознавство Державного стандарту базової середньої освіти конкретизує зміст історичного компоненту галузі та вимоги до загальноосвітньої підготовки учнів з історії. Основними компонентами змісту окремих курсів за цією програмою є: зміст історичного навчального матеріалу перелік державних вимог до рівня загальноосвітньої підготовки учнів на який учитель орієнтується під час вивчення конкретних тем відповідних курсів. До кожної теми надано...
80937. Види історичних документів, особливості їх вивчення 35.44 KB
  До історичних джерел належить все створене людиною, у тому числі результати його взаємодії з навколишнім середовищем, а також предмети матеріальної культури, звичаї, обряди, памятки писемності. У широкому сенсі слова памятники писемності в методиці називають документами
80938. Аналіз програми з історії України для 10-11 класів мета завдання та зміст курсу Нової історії України 35.68 KB
  Мета курсу за вибором Досліджуємо історію України для профільних класів суспільногуманітарного напряму поглиблення системи знань учнів про історію України XX століття яке забезпечується набуттям старшокласниками власного інтелектуального досвіду вивчення історичного матеріалу розвитком навчальнопізнавальних умінь та ключових предметних компетенцій. Реалізація курсу за вибором Досліджуємо історію України здійснена у контексті профілізації старшої школи допоможе виконати наступні завдання: поглибити цілісні уявлення старшокласників...
80939. Позакласна позашкільна робота з історії в загальноосвітній школі 30.73 KB
  Позакласна робота різноманітна освітня і виховна робота спрямована на задоволення інтересів і запитів дітей організована в позаурочний час педагогічним колективом школи. Позашкільна робота освітньовиховна діяльність позашкільних закладів для дітей та юнацтва.
80940. Побудова та використання на уроках історії України тренувальних та змістовних завдань 36.8 KB
  Наведіть приклад розроблених завдань. Під системою тренувальних завдань і вправ ми розуміємо сукупність послідовних завдань зі складністю що поступово зростає які повязані між собою спільною метою та змістом передбачають багаторазове виконання певної дії або діяльності метою набуття певного навику. Характерною ознакою системи тренувальних завдань та вправ є спрямованість на створення найбільш сприятливих умов для активної взаємодії субєкта з обєктом вивчення й забезпечення високої інтелектуальної активності субєкта що забезпечує...
80941. Етапи підготовки вчителя історії до уроку 36.49 KB
  визначення місця уроку в темі чи розділі його очікуваних результатів. добір методичних прийомів і засобів навчання відповідно до очікуваних результатів уроку та вибір методичного варіанта уроку, складання конспекту чи розгорнутого плану уроку.