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.


 

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

3386. Рассчитать и спроектировать резец для обработки наружной поверхности детали 8.03 MB
  Оправки в шпинделе закрепляют штоком, проходящим через шпиндель станка. Шток имеет на конце захватное устройство. Инструментальные оправки имеют соответствующие этому устройству наружные, внутренние или резьбовые поверхности захвата...
3387. Реконструкция многоквартирного крупноблочного дома серии 1-439А 888.5 KB
  При модернизации и реконструкции жилых зданий массовой застройки предусматривается решение следующих задач: приведение планировочной структуры здания в соответствие с требованиями к потребительским и эксплуатационным качествам современного ...
3388. Проект разработки роторного снегоочистителя 857.5 KB
  В процессе подготовки будущего инженера к самостоятельному решению технических и производственных задач одно из ведущих мест принадлежит курсовому проектированию. Цель данного курсового проекта – закрепить и обобщить теоретический мате...
3389. Проектирование редуктора и выбор типа зубчатых колес 353 KB
  Целью курсовой работы является получение навыков самостоятельного применения теоретических знаний для решения практических задач, связанных с техническим моделированием и созданием несложных технических устройств практического назначения. В...
3390. Контрольный тест по дисциплине Социология 133.5 KB
  Контрольный тест по дисциплине «Социология» для студентов дистанционного обучения Предлагаемый тест предназначен для контроля знаний, полученных студентами дистанционной формы обучения в процессе освоения курса общей социологии. Тест разработан в со...
3391. Жилищное строительство жилого здания 47 KB
  Введение Жилищное строительство в настоящее время характеризуется повышением стандарта жилища, переходом на новые улучшенные серии жилых домов с прогрессивными конструкциями. Данный курсовой проект «Жилое здание» выполнен в соответствии с задание на...
3392. Проектированию несложного гражданского малоэтажного здания 90.5 KB
  Введение Цель данной курсовой работы – обучение самостоятельному проектированию несложного гражданского здания с учётом основных факторов, влияющих на проектное решение. Выполнение курсовой работы позволяет систематизировать, закрепить и р...
3393. База данных Аэропорт 596 KB
  Введение Программное обеспечение для работы с базами данных используется на персональных компьютерах уже довольно давно. К сожалению, эти программы либо были элементарными диспетчерами хранения данных и не имели средств разработки прил...
3394. РЕЖИМЫ РАБОТЫ ОСНОВНОГО ОБОРУДОВАНИЯ ЭЛЕКТРОСТАНЦИЙ 3.69 MB
  Настоящее учебное пособие предназначено для студентов, изучающих курсы "Режимы работы основного оборудования" электрический станций и выполняющие дипломные, курсовые и УИР, связанные с вопросами использования оборудования ТЭС в переменных режимах работы...