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.


 

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

42318. Использование шаблонов при создании презентаций 191 KB
  На панели задач щелкните на кнопке Пуск Strt. В стартовом диалоговом окне щелкните на кнопке выбора Шаблон презентации Templte и затем на кнопке ОК. Примечание: Если вы продолжаете сеанс работы после предыдущего урока щелкните на меню Файл File и затем на команде Создать New. Щелкните на вкладке Дизайны презентаций Presenttion Designs.
42319. Информационные системы и системы управления базами данных 2.77 MB
  Информационные системы и системы управления базами данных Введение Информационные системы взаимодействия видов транспорта ИСВВТ отличаются от других информационных систем ИС в основном решаемыми задачами. Поэтому в основе любой из них лежит среда хранения обработки и доступа к данным база данных;  информационные системы ориентируются на конечного пользователя не обладающего высокой квалификацией в области применения вычислительной техники. Системы управленя базами данных Любая ИС оперирует информацией о той...
42320. Базы данных реляционных и объектно-реляционных СУБД 1.19 MB
  Рассмотрим смысл этих понятий на примере отношения таблицы СТУДЕНТЫсодержащего информацию о студентах некоторого вуза табл. Тип данных определяет диапазон значений которые можно сохранить в переменной или столбце таблицы отношения а также набор операций разрешенных для данных этого типа. Например предположим что в БД кроме таблицы СТУДЕНТЫ Табл. Допустим что столбец Имя таблицы СТУДЕНТЫ и столбец ФИО таблицы ПРЕПОДАВАТЕЛИ имеют одинаковые типы данных максимальную длину в обоих столбцах используется кириллица и смысл...
42321. Архитектура баз данных и способы доступа к ним в пакете Delphi 361.5 KB
  Архитектура баз данных Современная система управления базами данных такая как InterBse SQL Server пакета Delphi или Microsoft SQL Server 2000 может поддерживать хранение и обработку множества баз данных к которым одновременно могут обращаться множество пользователей. Прежде чем учиться управлению этими базами данных познакомимся с их структурой то есть с представлением базы данных на логическом и физическом уровнях. При этом будет рассмотрен список объектов поддерживаемых базами данных InterBse SQL Server 6 сокращённо...
42322. Операции с базой данных 238.5 KB
  Операции с базой данных Цель работы Изучить операции с базами данных в целом. Получить навыки использования приложения IBExpert для создания удаления регистрации подключения извлечения метаданных резервного копирования и восстановления базы данных СУБД Firebird. Изучить SQLоператоры для создания подключения и удаления базы данных. Исходные данные Студент получает индивидуальный вариант исходных данных который используется при выполнении всех лабораторных работ.
42323. Домены. SQL-операторы для работы с доменами 135.5 KB
  Домены Цель работы Изучить типы данных Firebird. Исходные данные Вариант исходных данных с кратким описанием предметной области получен студентом при выполнении первой лабораторной работы. Эта модель стала революционным событием в развитии баз данных . Элементы реляционной модели данных и формы их представления приведены в таблице 1.
42324. Таблицы. SQL-операторы для работы с таблицами и индексами 197.5 KB
  Изучить способы создания изменения и удаления таблиц. Теоретические сведения Таблицы Tbles Firebird реляционная СУБД поэтому все данные в Firebird хранятся в виде двумерных таблиц со строками и столбцами. Основные ограничения которым должны удовлетворять таблицы: Каждый столбец в таблице имеет уникальное имя. Первичный ключ это столбец который выбран для уникальной идентификации записей базы данных строк таблицы.
42325. Технология создания простейшей информационной системы 8.22 MB
  База данных должна содержать две таблицы: Товары и Приход товаров. Таблицы оперативной части ИС предназначены для работы с оперативной информацией значение которой актуально обычно только в течение короткого времени от момента поступления такой информации до момента окончания её обработки. Рабочая структура таблиц приведена ниже: Таблица Товары Название поля Смысл Тип Длина Tovr Наименование товара Строка 20 EdIzm Единица измерения Строка 10 Zen Цена за единицу измерения Целочисленный Таблица Приход товаров Название поля...
42326. Технология создания простейшей информационной системы (часть 2) 1.12 MB
  Например в компоненте DBGrid подчинённой таблицы отображается содержимое только тех строк подчинённой таблицы в которых содержимое поля внешнего ключа подчинённой таблицы ссылается на содержимое поля первичного ключа той строки главной таблицы на которую указывает курсор главной таблицы содержимое других строк подчинённой таблицы остаётся невидимым для пользователя. Для отказа от этого механизма визуализации в окне инспектора объектов компонента набор данных подчинённой таблицы в нашем случае это компонент Tble2 таблица Prihod...