Матрицы смежности и инцидентности
Ознакомление с формульным выражением симметричной квадратной матрицы. Определение свойств матриц смежности и инцидентности. Расчеты ориентированного мультиграфа при нулевой, либо линейной комбинации строк. Обзор теоремы ориентированного псевдографа.
| Рубрика | Математика |
| Вид | лекция |
| Язык | русский |
| Дата добавления | 18.10.2013 |
| Размер файла | 57,3 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Лекция
Матрицы смежности и инцидентности
Пусть D=(V,X) орграф.
V={v1,...,vn}, или X={x1,...,xm}.
Матрицей смежности орграфа D называется квадратная матрица A=[aij] порядка n, где:
Матрицей инцидентности называется матрица B=[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 - псевдограф без кратных ребер, матрица смежности - булева.
Маршруты и пути.
Последовательность:
- в которой чередуются вершины и ребра (дуги) и для каждого j=1,...,k ребро (дуга) xj имеет вид {vj,vj+1} (для орграфа (vj,vj+1)), называется маршрутом, соединяющим вершины v1 и vk+1 (путем из v1 в vk+1).
Пример:
v1, x1, v2, x2, v3, x4, v4, x3, v2 - маршрут,
x1, x2, x4, x3 - маршрут можно восстановить и по этой записи,
v1, v2, v3, v4, v2 - если кратности ребер (дуг) равны 1, то можно и так.
v2, x2, v3, x4, v4 - подмаршрут.
Число ребер в маршруте называется длиной маршрута (пути).
Маршрут (путь) называется замкнутым, если начальная вершина совпадает с конечной:
v1 = vk + 1
Незамкнутый маршрут (путь), в котором все ребра (дуги) попарно различны называется цепью.
Цепь, в которой все вершины попарно различны называется простой цепью.
Замкнутый маршрут (путь), в котором все ребра (дуги) попарно различны, называется циклом (контуром).
Цикл (контур), в котором все вершины попарно различны называется простым.
Теорема. В псевдографе G (в ориентированном псевдографе D) из всякого цикла (контура) можно выделить простой цикл (простой контур).
Доказательство (индукцией).
Пусть k - количество ребер, k+1 - количество вершин в цикле (или контуре).
При k=1 (петля) цикл всегда является простым.
Пусть утверждение верно для цикла длиной k-1.
Допустим, в цикле имеются совпадающие вершины: vi=vj, (если их нет, то цикл - простой).
Тогда удалим из цикла часть, заключенную между viи vj (вместе с vj). Получившийся цикл имеет меньшую длину и в силу индуктивного предположения из него можно выделить простой цикл.
Теорема. матрица мультиграф теорема
Из всякого незамкнутого маршрута (пути) можно выделить простую цепь с теми же начальной и конечной вершинами.
Доказательство аналогично предыдущему.
Определение. Композицией путей (маршрутов)
1 = v1, x1, v2, xk-1, vk.
2 = vk, xk, vk+1, xL-1, vL - называется путь (маршрут).
Размещено на Allbest.ru
...Подобные документы
Восстановление графов по заданным матрицам смежности вершин. Построение для каждого графа матрицы смежности ребер, инцидентности, достижимости, контрдостижимости. Поиск композиции графов. Определение локальных степеней вершин графа. Поиск базы графов.
лабораторная работа [85,5 K], добавлен 09.01.2009Понятие, типы и алгебра матриц. Определители квадратной матрицы и их свойства, теоремы Лапласа и аннулирования. Понятие обратной матрицы и ее единственность, алгоритм построения и свойства. Определение единичной матрицы только для квадратных матриц.
реферат [296,6 K], добавлен 12.06.2010Теоретико-множественная и геометрическая форма определения графов. Матрица смежностей вершин неориентированного и ориентированного графа. Элементы матрицы и их сумма. Свойства матрицы инцидентности и зависимость между ними. Подмножество столбцов.
реферат [81,0 K], добавлен 23.11.2008Основные операции над матрицами и их свойства. Произведение матриц или перемножение матриц. Блочные матрицы. Понятие определителя. Панель инструментов Матрицы. Транспонирование. Умножение. Определитель квадратной матрицы. Модуль вектора.
реферат [109,2 K], добавлен 06.04.2003Понятия теории графов. Понятия смежности, инцидентности и степени. Маршруты и пути. Матрицы смежности и инцедентности. Алгоритм поиска минимального пути в ненагруженном ориентированном орграфе на любом языке программирования, алгоритм фронта волны.
курсовая работа [466,3 K], добавлен 28.04.2011Построение диаграммы псевдографа, матрицы инцидентности и матрицы соседства вершин. Восстановление дерева по вектору с помощью алгоритма Прюфера. Построение таблицы истинности для функции и совершенной конъюнктивной и дизъюнктивной нормальной форм.
контрольная работа [181,9 K], добавлен 25.09.2013Ориентированные и неориентированные графы: общая характеристика, специальные вершины и ребра, полустепени вершин, матрицы смежности, инцидентности, достижимости, связности. Числовые характеристики каждого графа, обход в глубину и в ширину, базис циклов.
курсовая работа [225,5 K], добавлен 14.05.2012Понятие и типы матриц. Определители (детерминанты) квадратной матрицы и их свойства. Алгебраические действия над матрицами. Теоремы Лапласа и аннулирования. Понятие и свойства обратной матрицы, алгоритм ее построения. Единственность обратной матрицы.
курс лекций [336,5 K], добавлен 27.05.2010Построение логических взаимосвязей между цветами при помощи аппарата дискретной математики. Структуры объекта в виде множеств, граф отношений между ними. Исследование на рефлексивность, транзитивность, симметричность. Матрицы смежности и инцидентности.
контрольная работа [129,4 K], добавлен 07.06.2010Теория графов как раздел дискретной математики, исследующий свойства конечных множеств с заданными отношениями между их элементами. Основные понятия теории графов. Матрицы смежности и инцидентности и их практическое применение при анализе решений.
реферат [368,2 K], добавлен 13.06.2011Определение матрицы, характеристика основных ее видов. Правила транспонирования матриц. Элементы матрицы-произведения. Свойства определителей, примеры нахождения. Формулировка и следствие теоремы о ранге матрицы. Доказательство теоремы Кронекера-Капелли.
реферат [60,2 K], добавлен 17.06.2014Математическое описание системы автоматического управления с помощью графов. Составление графа и его преобразование, избавление от дифференциалов. Оптимизации ориентированных и неориентированных графов, составления матриц смежности и инцидентности.
лабораторная работа [42,2 K], добавлен 11.03.2012Описание заданного графа множествами вершин V и дуг X, списками смежности, матрицей инцидентности и смежности. Матрица весов соответствующего неориентированного графа. Определение дерева кратчайших путей по алгоритму Дейкстры. Поиск деревьев на графе.
курсовая работа [625,4 K], добавлен 30.09.2014Доказательство тождества с помощью диаграмм Эйлера-Венна. Определение вида логической формулы с помощью таблицы истинности. Рисунок графа G (V, E) с множеством вершин V. Поиск матриц смежности и инцидентности. Определение множества вершин и ребер графа.
контрольная работа [463,0 K], добавлен 17.05.2015Разработка логико-формальной модели описания методики изготовления винных изделий. Разделение ингредиентов и продукции на множества. Исследование на рефлексивность, транзитивность, симметричность. Построение графа, матрицы смежности и инцидентности.
контрольная работа [165,2 K], добавлен 07.06.2010Размеры прямоугольной, квадратной, диагональной, скалярной матриц. Линейные операции над матрицами. Умножение строки на столбец (скалярное произведение). Транспонирование матрицы, ее элементы. Образование треугольной таблицы, состоящей из строк, столбцов.
презентация [1,4 M], добавлен 03.12.2016Понятие матрицы, прямоугольная матрица размера m x n - совокупность mn чисел, расположенных в виде прямоугольной таблицы, содержащей m строк и n столбцов. Численная характеристика квадратной матрицы - ее определитель. Действия над матрицами, ранг матрицы.
реферат [87,2 K], добавлен 01.08.2009Понятие обратной матрицы. Пошаговое определение обратной матрицы: проверка существования квадратной и обратной матрицы, расчет определителя и алгебраического дополнения, получение единичной матрицы. Пример расчета обратной матрицы согласно алгоритма.
презентация [54,8 K], добавлен 21.09.2013Интерпретация ортогональной и унитарной матрицы. Основные детерминанты матриц. Определение комплексных квадратных невырожденных и вырожденных матриц. Методы нахождения определителя. Метод конденсации Доджсона. Кососимметричная полилинейная функция строк.
курсовая работа [620,9 K], добавлен 04.06.2015Граф как совокупность объектов со связями между ними. Характеристики ориентированного и смешанного графов. Алгоритм поиска кратчайшего пути между вершинами, алгоритм дейкстры. Алгебраическое построение матрицы смежности, фундаментальных резервов и циклов.
методичка [29,4 M], добавлен 07.06.2009
