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.


 

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

36662. Облік товарно-матеріальних запасів. Система обліку та методи оцінки товарно-матеріальних запасів 97 KB
  Товарно-матеріальними запасами вважаються: товари, які були куплені підприємством і зберігаються на складі для наступної реалізації: готова продукція, напівфабрикати та незавершене виробництво: різні матеріали, що зберігаються на складі і призначені для переробки в процесі виробництва або для забезпечення виробничого процесу.
36663. Організаційно-методичні принципи сертифікації в Україні 115 KB
  Прискоренню розвитку національної системи сертифікації сприяє активне міжнародне співробітництво України в галузі технічного регулювання, безпосередня участь у роботі міжнародних і регіональних організацій та їх технічних комітетів.
36664. Термореактивные полимеры и материалы на их основе 59.5 KB
  Термореактивные полимеры (смолы) применяются в качестве связующих веществ, в которые вводят обычно отвердители, наполнители, пластификаторы и другие модифицирующие добавки. Основными требованиями к связующим веществам являются: высокая клеящая способность (адгезия)
36665. Фінансова звітність, її зміст та інтерпретація 250 KB
  Методика аналізу фінансового стану підприємства на базі звітності. Фінансова звітність це система взаємоповязаних узагальнюючих показників що відображають фінансовий стан підприємства установи організації та результати діяльності за звітний період. Таблиця 1 Призначення компонентів фінансової звітності Компонент Призначення Баланс Інформація про фінансове становище підприємства на певну дату. Звіт про прибутки та збитки Інформація про доходи витрати та фінансові результати діяльності підприємства за звітний період Звіт про зміни у...
36666. Загальноприйняті принципи і системи обліку 255.5 KB
  Загальноприйняті принципи і системи обліку. ПЛАН Роль обліку в системі управління користувачі облікової інформації. Загальноприйняті принципи бухгалтерського обліку. Міжнародні організації зі стандартизації бухгалтерського обліку і звітності Склад та загальна характеристика міжнародних стандартів бухгалтерського обліку.
36667. Педагогіка вищої школи. Тексти лекцій 179.46 KB
  Структура методів навчання за джерелами знань ПЕДАГОГІЧНА МАЙСТЕРНІСТЬ Моральнодуховні якості гуманістична спрямованість; національна гідність; інтелігентність; життєві ідеали; совісність; чесність; правдивість; обєктивність; толерантність. Професійні знання навчального предмета; анатомії і фізіології людини; психології; педагогіки; методики навчання. pais дитя ago веду керую наука про навчання та виховання дітей.
36668. ПРОЕКТИРОВАНИЕ ПРЕДПРИЯТИЙ АВТОМОБИЛЬНОГО ТРАНСПОРТА 773.5 KB
  Стоимость зданий и сооружений по подгруппам производственные здания административнобытовые помещения складские помещения закрытая стоянка трансформаторная компрессорная склад газовых баллонов прочие отапливаемые помещения открытая стоянка определяется по формуле: Цз=цзi Vзi 1 где Цз общая стоимость зданий и сооружений руб м3; цзi стоимость одного м3 iой группы зданий или сооружений руб м3; Vзi объем iой подгруппы зданий м3; N количество всех оцениваемых зданий и сооружений ед. Стоимость открытой стоянки и затраты...
36669. Термодинамика и тепломассообмен 2.83 MB
  Первоначально же в середине XIX века она возникла как техническая термодинамика изучающая закономерности взаимного превращения теплоты в механическую работу и являющаяся теоретическим 4ундаментом теплотехники. На ее основе производится расчет и проектирование технологического оборудования для осуществления процессов деформации сушки термообработки и других формируются методы прямого преобразования теплоты в электрическую энергию проводится анализ эффективности термодинамических циклов процессов теплообмена изучаются...
36670. ТЕОРИЯ АВТОМАТИЧЕСКОГО УПРАВЛЕНИЯ Линейные системы управления 5.19 MB
  В учебном пособии излагаются методы анализа и синтеза линейных линеаризованных систем автоматического управления САУ базирующиеся на применении принципа обратной связи по выходной управляемой координате или по вектору координат состояния объекта управления. Продемонстрированы современные методы математического описания линейных объектов и систем во временной и частотной области показана взаимосвязь различных методов описания приведены наиболее распространенные в инженерной практике методы анализа и синтеза непрерывных и дискретных...