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.


 

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

49853. Метод вольт-фарадных характеристик барьера 1.96 MB
  Методы определения подвижности носителей заряда Методы определения времени жизни Введение. Метод является основным при контроле концентрации носителей заряда в эпитаксиальных слоях выращенных на сильнолегированной или полуизолирующей подложках. для концентрации свободных носителей Nx = [2 eεε02][d1 C2 dU]–1. Таким образом измеряя зависимость емкости барьера от напряжения смещения U можно вычислить концентрацию свободных носителей Nx которая для неоднородного полупроводника зависит от глубины x на которую проникает объемный...
49854. Оптимизация рабочего процесса двигателя 4ЧН8,2/7 2.07 MB
  Описание объекта исследования Оптимизация рабочего процесса Проектирование турбокомпрессора Газодинамический расчет компрессора Профилирование основных элементов турбокомпрессора Рабочее колесо компрессора
49855. Расчет вала електродвигателя 890.5 KB
  Вычисление частоты вращения вала электродвигателя Диаметр звездочки Частота вращения приводного вала Перeдаточное число для червячной передачи U=34.4 Частота вращения вала электродвигателя Выбирается двигатель АИР 80В4 с частотой вращения ротора и мощностью . Распределение мощности по валам: Частота вращения: Крутящий момент Скорость скольжения Выбираем материал третьей группы СЧ1532 Коэффициент нагрузки: Предварительное межосевое расстояние: Принимаем .1 аДля быстроходного вала из рекомендации выбрано: Выбираем Диаметр вала...
49856. ОБОСНОВАНИЕ КОНФИГУРАЦИИ ПЕРСОНАЛЬНОГО КОМПЬЮТЕРА ЦЕЛЕВОГО НАЗНАЧЕНИЯ 505.66 KB
  Структура ПК Внешний блок питания 150W Принтер Cnon iSENSYS LBP6000 Клавиатура Crown CMKM 3008 Корпус Morex T3500B 150W Blck Жесткий диск Segte ST250LM004 Материнская платапроцессорвидеозвуксеть Intel D410PT Компьютерная мышь Crown CMKM 3008 Монитор CER B173DO Оперативная память Kingston KVR800D2N6 2G Список источников информации http: ru.org wiki MiniITX http: ru.org wiki tx http: www.php http: www.
49857. Расчет приводного вала ленточного конвеера 1.08 MB
  Расчет КПД привода: где КПД клиноременной передачи КПД зубчатой передачи – КПД подшипников Определение требуемой мощности электродвигателя. Определение частоты вращения приводного вала ленточного конвеера. Принимаем n=77 oб. определение передаточного числа: Принимаем по табл.1 Коэффициент приведения для расчетов на контактную выносливость: на изгибную...
49858. Конструкции режущего и вспомогательного инструмента общего и специального назначения 603.17 KB
  Задачами проекта являются закрепление навыков проектирования технологических операций резанием расчета режимов резания проектирования вспомогательных инструментов рационального выбора режущих инструментов и составления их рабочих чертежей работы с технической литературой и каталогами ведущих инструментальных фирм. Выполнить его сборочный чертеж дать в записке описание работы приспособления его конструктивных особенностей выполнить необходимые расчеты выполнить рабочий чертеж корпусной детали разработанного...
49859. Расчет мощности электродвигателя и его составляющих 559.5 KB
  Выберем расчетную частоту вращения вала электродвигателя, методом подбора по оптимальному значению передаточного числа. Рекомендуемые пределы значений для соосного двухступенчатого редуктора
49860. Расчет привода электродвигателя АИР132М8 1.01 MB
  Расчёт производим в форме проверки коэффициента запаса прочности, значение которого можно принять. При этом должно выполняться условие, что, где – расчётный коэффициент запаса прочности, и – коэффициенты запаса по нормальным и касательным напряжениям, которые определим ниже.