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.


 

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

81363. Визнання та виконання рішень іноземних судів і арбітражі 23.62 KB
  Закону порядок виконання в Україні рішень іноземних судів і арбітражів встановлюється відповідними міжнародними договорами України цим Законом та іншими законами України. Клопотання про визнання і виконання рішення іноземного суду розглядається компетентним судом і після винесення ухвали про визнання та прийняття до виконання рішення іноземного суду на території України виписується виконавчий лист що і є основою для провадження виконавчих дій. Основою для виконання рішення іноземного арбітражу є наказ господарського суду та ухвала...
81364. Відповідальність за невиконання рішення, що зобов’язує боржника виконати певні дії, та рішення про поновлення на роботі 22.33 KB
  89 Закону у разі невиконання без поважних причин у встановлений державним виконавцем строк рішення що зобовязує боржника виконати певні дії та рішення про поновлення на роботі державний виконавець виносить постанову про накладення штрафу на боржника фізичну особу від десяти до двадцяти неоподатковуваних мінімумів доходів громадян; на посадових осіб від двадцяти до сорока неоподатковуваних мінімумів доходів громадян; на боржника юридичну особу від сорока до шістдесяти неоподатковуваних мінімумів доходів громадян та встановлює новий...
81365. Звільнення майна боржника з-під арешту, зняття арешту 27.57 KB
  Особа яка вважає що майно на яке накладено арешт належить їй а не боржникові може звернутися до суду з позовом про визнання права на майно і про звільнення майна зпід арешту. У разі прийняття судом рішення про звільнення майна зпід арешту або сплати боржником повної суми боргу за виконавчим документом до реалізації арештованого майна боржника майно звільняється зпід арешту за постановою державного виконавця яка затверджується начальником відповідного органу державної виконавчої служби додаток 40 не пізніше наступного дня коли...
81366. Поняття виконавчого провадження та його місце в системі права України 24.12 KB
  Виконавче провадження це врегульовані законодавством України суспільні відносини що виникають і реалізуються в процесі примусового виконання між органами державної виконавчої служби і посадовими особами які здійснюють примусову реалізацію рішень ухвал постанов судових і несудових органів з одного боку та між особами котрі беруть участь у виконавчому провадженні і залучаються до проведення виконавчих дій з другого боку на підставах у спосіб та в межах встановлених законом. Закону України Про виконавче провадження визначає...
81367. Принципи виконавчого провадження : поняття, зміст та значення 30.61 KB
  Принципи виконавчого провадження це закріплені у правових нормах основні засади керівні положення які визначають організацію органів державної виконавчої служби зміст і спрямованість її діяльності правовий статус учасників виконавчого провадження. На підставі теоретичних положень аналізу чинного законодавства та практики його застосування можна виокремити такі принципи виконавчого провадження: принцип гуманізма полягає у тому що заборонено у будьякій формі посягати на права і свободи фізичних осіб які беруть участь у виконавчому...
81368. Поняття, сутність та елементи правовідносин у виконавчому провадженні 28.23 KB
  Правовідносини у виконавчому провадженні виникають між державним виконавцем з одного боку та іншими субєктами виконавчого провадження стягувачем боржником з іншого. До ознак правовідносин що виникають у виконавчому провадженні слід віднести такі: вони виникають при примусовому виконанні рішень судів та інших юрисдикційних органів та регламентовані законодавством про виконавче провадження; без волі стягувана фізичної або юридичної особи державний виконавець не має права відкривати виконавче провадження. У випадку звернення...
81369. Суб’єкти виконавчого провадження та їх класифікація 25.45 KB
  Субєкти виконавчого провадження субєкти виконавчих правовідносин учасники виконавчого провадження це носії процесуальних прав та обовязків у виконавчому провадженні. Закону учасниками виконавчого провадження є державний виконавець сторони представники сторін прокурор експерти спеціалісти перекладачі субєкти оціночної діяльності субєкти господарювання. Прокурор бере участь у виконавчому провадженні у випадку здійснення представництва інтересів громадянина або держави в суді та відкриття виконавчого провадження на підставі...
81370. Органи і посадові особи Державної виконавчої служби, їх правове становище та повноваження 24.9 KB
  Органами державної виконавчої служби є: Департамент державної виконавчої служби Міністерства юстиції України до складу якого входить відділ примусового виконання рішень; управління державної виконавчої служби Головного управління юстиції Міністерства юстиції України в Автономній Республіці Крим головних управлінь юстиції в областях містах Києві та Севастополі до складу яких входять відділи примусового виконання рішень; районні районні у містах міські міст обласного значення міськрайонні відділи державної виконавчої служби відповідних...
81371. Державний виконавець як обов’язковий суб’єкт виконавчого провадження, його обов’язки та права 29.09 KB
  Державний виконавець у процесі здійснення виконавчого провадження має право: проводити перевірку виконання боржниками рішень що підлягають виконанню відповідно до цього Закону; здійснювати перевірку виконання юридичними особами всіх форм власності фізичними особами фізичними особами підприємцями рішень стосовно працюючих у них боржників; з метою захисту інтересів стягувача одержувати безоплатно від органів установ організацій посадових осіб сторін та учасників виконавчого провадження необхідні для проведення виконавчих дій...