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.


 

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

22261. МОЗГОВОЙ КРОВОТОК 66.5 KB
  Торакальная и люмбальная порции спинного мозга не имеют в такой степени расширенного кровотока. Цереброваскулярное сосудистое русло постоянно находится под влиянием определенного количества физических и химических стимулов которые алаптируют калибр мозговых сосудов потребностям различных отделов головного мозга в зависимости от их функциональной активности. Конечной целью присходящих процессов яваляется: поддержание и быстрое изменение локального МК в зависимости от метаболической потребности различных отделов головного мозга; обеспечение...
22262. ИНФЕКЦИОННЫЕ БОЛЕЗНИ (ИБ) 43.5 KB
  Легкая форма гриппа характеризуется острым катаром верхних дыхательных путей. Эта форма длится несколько дней и завершается полным выздоровлением. Тяжелая форма гриппа имеет две разновидности: первая связана с резкой интоксикацией вторая легочными осложнениями при присоединении вторичной инфекции. Папулопустулезная форма характеризуется появлением на коже сыпи в виде узелков папула и гнойничков пустула на лице голове шее груди спине.
22263. КИШЕЧНЫЕ ИНФЕКЦИИ (КИ) 40.5 KB
  ДИЗЕНТЕРИЯ ШИГЕЛЛЕЗ острое кишечное инфекционное заболевание с поражением толстой кишки и признаками интоксикации антропоноз. Шигеллы размножаются в энтероцитах толстой кишки что ведет к некрозу клеток. Местные изменения развиваются в слизистой толстой кишки в основном в прямой и сигмовидной что проявляется дизентерийным колитом. Просвет кишки сужен.
22264. Совершенствование системы документооборота в ООО «РАЙЖИВСОЮЗ» 242 KB
  Дать определение понятия «документооборот», определить какие существуют виды документооборота, и какие функции они выполняют. Разобрать теоретические аспекты данной темы; Дать полную характеристику организации (ООО «РАЙЖИВСОЮЗ»), на основе которой будет выполняться данная курсовая работа; Предложить методы совершенствования существующей системы документооборота организации, показать и доказать их экономическую эффективность.
22265. ОПУХОЛИ СИСТЕМЫ КРОВИ (ГЕМОБЛАСТОЗЫ) 39 KB
  Это происходит следующим образом: сначала лейкозные клетки разрастаются в органах кроветворения красный костный мозг селезенка лимфоузлы затем происходит выход лейкозных клеток в кровь где их можно обнаружить в большом количестве на следующем этапе который рассматривается как метастазирование лейкозные клетки из крови попадают в органы и образуют лейкозные инфильтраты по ходу сосудов в строме что ведет к атрофии и дистрофии органа. лейкозные клетки вытесняют нормальные клетки крови эритроциты лейкоциты тромбоциты...
22266. ЗЛОКАЧЕСТВЕННЫЕ ЛИМФОМЫ 27 KB
  Лимфосаркома злокачественная опухоль из клеток лимфоцитарного ряда. Микро характерно диффузное разрастание атипичных лимфоидных клеток которые могут выходить за пределы ткани лимфоузла т. За счет пролиферации опухолевых клеток рисунок лимфоузла стирается в ткани возникают очаги некроза и склероза. Они состоят из пролиферирующих лимфоидных клеток гистиоцитов плазмоцитов и атипичных клеток.
22267. НАРУШЕНИЯ КРОВООБРАЩЕНИЯ. ПОЛНОКРОВИЕ (ГИПЕРЕМИЯ) 43.5 KB
  Это проявляется асцитом расширением вен передней брюшной стенки голова Медузы расширением вен пищевода что опасно кровотечением. КРОВОТЕЧЕНИЕ ГЕМОРРАГИЯ Определение кровотечение геморрагия это выход крови из просвета сосуда или полости сердца наружу наружное кровотечение или в полости тела внутреннее кровотечение. Наружное кровотечение: кровохарканье кровотечение из носа рвота кровью маточное кровотечение метроррагия мелена кровь с калом.
22268. НАРУШЕНИЯ КРОВООБРАЩЕНИЯ. Тромбоз 42.5 KB
  Неблагоприятный: септический аутолиз тромба рассасывание тромба под действием микробов что опасно сепсисом и кровотечением отрыв тромба тромбоэмболия которая может привести к инфаркту. Значение: тромбоз может привести к нарушению кровоснабжения органа и развитию инфаркта гангрены. ТЭЛА может привести к красному инфаркту легкого или к внезапной смерти. ИНФАРКТ Определение: инфаркт это сосудистый ишемический некроз который возникает вследствие прекращения...
22269. Некроз. Патогенетические формы 33 KB
  Этиологические формы: токсический некроз эта форма встречается при действии на ткани организма токсинов яды биологи ческой природы токсины палочки дифтерии бактерий или химической природы кислоты щелочи. травматический некроз этот некроз возникает при действии сильных физических факторов высокие или низкие температуры электроток. сосудистый некроз связан с острым нарушением кровоснабжения органа или ткани.