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.


 

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

15543. Законодательство Российской Федерации о рекламе 37 KB
  Законодательство Российской Федерации о рекламе Законодательство Российской Федерации о рекламе состоит из настоящего Федерального закона. Отношения возникающие в процессе производства размещения и распространения рекламы могут регулироваться также принятыми в с
15544. Общие требования к рекламе 138.5 KB
  5. Общие требования к рекламе1. Реклама должна быть добросовестной и достоверной. Недобросовестная реклама и недостоверная реклама не допускаются.2. Недобросовестной признается реклама которая:1 содержит некорректные сравнения рекламируемого товара с находящимися в обо...
15545. Защита несовершеннолетних в рекламе 25.5 KB
  6. Защита несовершеннолетних в рекламеВ целях защиты несовершеннолетних от злоупотреблений их доверием и недостатком опыта в рекламе не допускаются:1 дискредитация родителей и воспитателей подрыв доверия к ним у несовершеннолетних;2 побуждение несовершеннолетних к то
15546. Товары, реклама которых не допускается 84 KB
  7. Товары реклама которых не допускаетсяНе допускается реклама:1 товаров производство и или реализация которых запрещены законодательством Российской Федерации;2 наркотических средств психотропных веществ и их прекурсоров;3 взрывчатых веществ и материалов за исклю
15547. Реклама товаров при дистанционном способе их продажи 18.5 KB
  8. Реклама товаров при дистанционном способе их продажиВ рекламе товаров при дистанционном способе их продажи должны быть указаны сведения о продавце таких товаров: наименование место нахождения и государственный регистрационный номер записи о создании юридического ли...
15548. Реклама о проведении стимулирующих мероприятий 14.5 KB
  9. Реклама о проведении стимулирующих мероприятийВ рекламе сообщающей о проведении стимулирующей лотереи конкурса игры или иного подобного мероприятия условием участия в которых является приобретение определенного товара далее стимулирующее мероприятие должны б...
15549. Социальная реклама 43.5 KB
  10. Социальная реклама1. Рекламодателями социальной рекламы могут выступать физические лица юридические лица органы государственной власти иные государственные органы и органы местного самоуправления а также муниципальные органы которые не входят в структуру органо
15550. Срок действия рекламы, признаваемой офертой 19.5 KB
  11. Срок действия рекламы признаваемой офертойЕсли в соответствии с Гражданским кодексом Российской Федерации реклама признается офертой такая оферта действует в течение двух месяцев со дня распространения рекламы при условии что в ней не указан иной срок.Комментируем...
15551. Сроки хранения рекламных материалов 24 KB
  12. Сроки хранения рекламных материаловРекламные материалы или их копии в том числе все вносимые в них изменения а также договоры на производство размещение и распространение рекламы должны храниться в течение года со дня последнего распространения рекламы или со дня о