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.


 

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

17897. Природно-ресурсний потенціал сучасного світового господарства 79 KB
  Лекція 5. Природноресурсний потенціал сучасного світового господарства 1. Територія сільськогосподарські угіддя До природних ресурсів що все ширше використовуються в ході розвитку суспільства і створюють умови його існування в першу чергу відноситься земля. Зем
17898. Людські ресурси світового господарства 90 KB
  Лекція 6. Людські ресурси світового господарства 1. Чисельність і темпи зростання населення Землі Дані про чисельність населення отримують на основі регулярних загальних переписів населення що проводяться зазвичай один раз в 10 років а в проміжках між ними шляхом р...
17899. Науково-технічний потенціал і його роль в розвитку сучасного світового господарства 78.5 KB
  Лекція 7. Науковотехнічний потенціал і його роль в розвитку сучасного світового господарства 1. Загальне поняття і критерії оцінки науковотехнічного потенціалу Дія науковотехнічного прогресу на розвиток економіки і всіх сфер діяльності людського суспільства в су...
17900. Загальне поняття галузевої структури і роль сучасної промисловості в світовому господарстві 46 KB
  Лекція 8. Загальне поняття галузевої структури і роль сучасної промисловості в світовому господарстві 1. Загальне поняття галузевої структури Структура економіки багатопланове поняття розглядати яке можна з різних точок зору та яке показує співвідношення різних ...
17901. Сучасний стан і перспективи розвитку в головних галузевих комплексів світової економіки 105 KB
  Лекція 9. Сучасний стан і перспективи розвитку в головних галузевих комплексів світової економіки 1. Паливноенергетичний комплекс ПЕК його структура і тенденція розвитку Галузі ПЕК відносяться до капіталомістких галузей. У промисловості розвинених країнах де пред...
17902. Чинники, які впливають на міжнародні економічні позиції країни 58.5 KB
  ЕКОНОМІЧНА БЕЗПЕКА КРАЇНИ Лекція 10. Чинники які впливають на міжнародні економічні позиції країни Будьяка нація є складовою частиною світу. Якби не було прагнення яке можуть проявляти окремі країни якби не було бажання переважної більшості інших країн створити у ...
17903. Економічна безпека країни 75.5 KB
  Лекція 11. Економічна безпека країни 11.1. Поняття економічної безпеки Економічна безпека це стан національної економіки що забезпечує задоволення життєво важливих потреб країни в матеріальних благах незалежно від виникнення в світовій економічній системі або усере...
17904. ТЕОРЕТИЧЕСКИЕ И ОРГАНИЗАЦИОННЫЕ ОСНОВЫ НАЛОГОВОГО МЕНЕДЖМЕНТА 336 KB
  Тема № 1 Теоретические и организационные основы налогового менеджмента. План 1. Сущность налогового менеджмента как необходимого элемента налогового права. 2. Фискальный мониторинг. 3. Государственный налоговый менеджмент. 4. Корпоративный налог
17905. Учет плательщиков налогов 113.5 KB
  Тема № 2 Учет плательщиков налогов Организация учета плательщиков налогов Государственный реестр физических лиц плательщиков налогов. 3. Порядок подачи документов СПД для взятия их на учет учет плательщиков Учет плательщиков НДС. АРМ Учет ...