1.2 Основные термины и теоремы теории графов - Определение кратчайшего пути в графе
- 1. Граф - Пара объектов G = ( X, Г ),где Х - конечное множество, а Г - конечное подмножество прямого произведения Х*Х. При этом Х называется множеством вершин, а Г - множеством дуг графа G. 2. Любое конечное множество точек (вершин), некоторые из которых попарно соединены стрелками, (в теории графов эти стрелки называются дугами), можно рассматривать как граф. 3. Если в множестве Г все пары упорядочены, то такой граф называют Ориентированным . 4. Дуга- ребро ориентированного графа. 5. Граф называется Вырожденным, если у него нет ребер. 6. Вершина Х называется Инцидентной ребру G, если ребро соединяет эту вершину с какой-либо другой вершиной. 7. Подграфом G(V1, E1) графа G(V, E) называется граф с множеством вершин V1 НV и множеством ребер (дуг) E1Н E, - такими, что каждое ребро (дуга) из E1 Инцидентно (инцидентна) только вершинам из V1 . Иначе говоря, подграф содержит некоторые вершины исходного графа и некоторые ребра (только те, оба конца которых входят в подграф). 8. Подграфом, порожденным множеством вершин U называется подграф, множество вершин которого - U, содержащий те и только те ребра, оба конца которых входят в U. 9. Подграф называется Остовным подграфом, если множество его вершин совпадает с множеством вершин самого графа. 10. Вершины называются Смежными, если существует ребро, их соединяющее. 11. Два ребра G1 и G2 называются Смежными, если существует вершина, инцидентная одновременно G1 и G2. 12. Каждый граф можно представить в пространстве множеством точек, соответствующих вершинам, которые соединены линиями, соответствующими ребрам (или дугам - в последнем случае направление обычно указывается стрелочками). - такое представление называется Укладкой графа. 13. Доказано, что в 3-мерном пространстве любой граф можно представить в виде укладки таким образом, что линии, соответствующие ребрам (дугам) не будут пересекаться во внутренних точках. Для 2-мерного пространства это, вообще говоря, неверно. Допускающие представление в виде укладки в 2-мерном пространстве графы называют Плоскими (планарным). 14. Другими словами, Планарным называется граф, который может быть изображен на плоскости так, что его ребра не будут пересекаться. 15. Гранью графа, изображенного на некоторой поверхности, называется часть поверхности, ограниченная ребрами графа.
Данное понятие грани, по - существу, совпадает с понятием грани многогранника. В качестве поверхности в этом случае выступает поверхность многогранника. Если многогранник выпуклый, его можно изобразить на плоскости, сохранив все грани. Это можно наглядно представить следующим образом: одну из граней многогранника растягиваем, а сам многогранник "расплющиваем" так, чтобы он весь поместился внутри этой грани. В результате получим плоский граф. Грань, которую мы растягивали "исчезнет", но ей будет соответствовать грань, состоящая из части плоскости, ограничивающей граф.
Таким образом, можно говорить о вершинах, ребрах и гранях многогранника, а оперировать соответствующими понятиями для плоского графа.
- 16. Пустым называется граф без ребер. Полным называется граф, в котором каждые две вершины смежные. 17. Конечная последовательность необязательно различных ребер E1,E2,...EN называется Маршрутом длины n, если существует последовательность V1, V2, ... VN необязательно различных вершин, таких, что EI = (VI-1,VI ). 18. Если совпадают, то маршрут Замкнутый. 19. Маршрут, в котором все ребра попарно различны, называется Цепью. 20. Замкнутый маршрут, все ребра которого различны, называется Циклом. Если все вершины цепи или цикла различны, то такая цепь или цикл называются Простыми. 21. Маршрут, в котором все вершины попарно различны, называется Простой цепью. 22. Цикл, в котором все вершины, кроме первой и последней, попарно различны, называется Простым циклом. 23. Граф называется Связным, если для любых двух вершин существует путь, соединяющий эти вершины. 24. Любой максимальный связный подграф (то есть, не содержащийся в других связных подграфах) графа G называется Компонентой связности. Несвязный граф имеет, по крайней мере, две компоненты связности. 25. Граф называется K - Связным (K - реберно - связным), Если удаление не менее K вершин (ребер) приводит к потере свойства связности. 26. Маршрут, содержащий все вершины или ребра графа и обладающий определенными свойствами, называется Обходом графа. 27. Длина маршрута (цепи, простой цепи) равна количеству ребер а порядке их прохождения. Длина кратчайшей простой цепи, соединяющей вершины vI и vJ В графе G, называется Расстоянием d (vI, vJ) между vI И vJ. 28. Степень вершины - число ребер, которым инцидентна вершина V, обозначается D(V).
С помощью различных операций можно строить графы из более простых, переходить от графа к более простому, разбивать графы на более простые и т. д.
Среди одноместных операций наиболее употребительны: удаление и добавление ребра или вершины, стягивание ребра (отождествление пары смежных вершин), подразбиение ребра (т. е. замена ребра (U, V) на пару (U, W), (W, V), где W - новая вершина) и др.
Известны двуместные операции: соединение, сложение, различные виды умножений графов и др. Такие операции используются для анализа и синтеза графов с заданными свойствами.
29. Два графа G1=(V1;E1), G2=(V2;E2),называются Изоморфными, если существует взаимнооднозначное соответствие между множествами вершин V1 и V2 И между множествами ребер Е1 и Е2, такое, чтобы сохранялось отношение инцидентности.
Понятие изоморфизма для графов имеет наглядное толкование. Представим ребра графов эластичными нитями, связывающими узлы - вершины. Тогда, изоморфизм можно представить как перемещение узлов и растяжение нитей.
Теорема 1.
Пусть задан граф G=(V;E),где V - множество вершин, E - множество ребер, тогда 2[E]=У(V), т. е. удвоенное количество ребер равно сумме степеней вершин.
Теорема 2. (Лемма о рукопожатиях)
В конечном графе число вершин нечетной степени четно.
Теорема 3.
Граф связен тогда и только тогда, когда множество его вершин нельзя разбить на два непустых подмножества так, чтобы обе граничные точки каждого ребра находились в одном и том же множестве.
Расстоянием между двумя вершинами связного графа называется длина кратчайшей цепи, связывающей эти вершины (в количестве ребер).
Свойства связных графов.
- 1. Связный граф остается связным после удаления ребра тогда и только тогда, когда это ребро содержится в цикле. 2. Связный граф, имеющий К вершин, содержит по крайней мере К-1 ребро. 3. В связном графе любые две простые цепи максимальной длины имеет по крайней мере одну общую вершину. 4. В графе с N вершинами и К компонентами связности число ребер не превышает 1/2(N-K)(N-K+1). 5. Пусть у графа G есть N вершин. Пусть D(G)- минимальная из степеней вершин этого графа. Тогда D(G) > 1/2 (N-1). 30. Связный граф без циклов называется Деревом.
Деревья особенно часто возникают на практике при изображении различных иерархий. Например, популярные генеалогические деревья.
Пример(генеалогическое дерево): На рисунке показано библейское генеалогическое дерево.
Эквивалентные определения дерева.
- 1. Связный граф называется деревом, если он не имеет циклов. 2. Содержит N-1 ребро и не имеет циклов. 3. Связный и содержит N-1 ребро. 4. Связный и удаление одного любого ребра делает его несвязным. 5. Любая пара вершин соединяется единственной цепью. 6. Не имеет циклов и добавление одного ребра между любыми двумя вершинами приводит к появлению одного и только одного цикла.
Раскраска графов
Раскраской графа G = (V, E) называется отображение D: V N . Раскраска называется Правильной, если образы любых двух смежных вершин различны: D (U) ? D (V), если (U,V) I. Хроматическим числом графа называется минимальное количество красок, необходимое для правильной раскраски графа.
Теорема 5.
Граф является планарным тогда и только тогда, когда он не содержит подграфа, изоморфного одному из следующих (графы Понтрягина - КуратовскОго).
Граф К33 Граф К5
Свойство: В любом планарном графе существует вершина, степень которой<=5.
Способы задания графов:
1. Геометрический:
2. Матрица смежности:
Матрица смежности - квадратная матрица, размерности, равной количеству вершин. При этом а[ i, j ]-целое число, равное количеству ребер, связывающих i-ю, j-ю вершину. Если в графе нет петель, то диагональные элементы равны 0.
Если ребра не повторяются, то все элементы 0 или 1. Если граф неориентированный, то матрица симметрична.
3. Матрица инцидентности:
A |
В |
С |
D | |
A |
1 |
1 |
0 |
0 |
B |
0 |
1 |
1 |
0 |
C |
1 |
0 |
1 |
0 |
D |
0 |
0 |
1 |
1 |
4. Явное задание графа как алгебраической системы:
<{A, b, c, d},{U, v, w, x}; {(U, a),(U, b),(V, b),(V, c),(W, c),(W, a),(X, c), (X, d)}>.
Так как мы рассматриваем только простые графы, граф нам проще определять как модель, носителем которой является множество вершин, а отношение - бинарное отношение смежности вершин. Тогда данный граф запишется как <{A, b, c, d}; {(A, b), (B, a),(B, c),(C, b),(A, c),(C, a),(C, d),(D, c)}>. В таком представлении ребру соответствуют две пары вершин (V1,v2) и (V2,v1), инцидентных данному ребру. Чтобы задать такое представление, достаточно для каждого ребра указать двухэлементное множество вершин - его мы и будем отождествлять с ребром. Для данного графа ребра задаются множеством [1] и граф мы будем записывать как пару (V, E), где V - множество вершин, а E - множество ребер.
5. Наконец, граф можно задать посредством списков.
Например:
Вариант 1: списком пар вершин, соединенных ребрами (или дугами);
Вариант 2: списком списков для каждой вершины множества смежных с ней вершин.
- [1] A, b},{B, c},{A, c},{C, d
Похожие статьи
-
Теория Графов, 1.1 Историческая справка - Определение кратчайшего пути в графе
Граф дискретный программирование 1.1 Историческая справка ТЕОРИЯ ГРАФОВ - это область дискретной математики, особенностью которой является геометрический...
-
Основные определения, термины и понятия - Визуализация графа цитирования
1. Граф - совокупность множества вершин и наборов пар вершин, называемых ребрами. 2. Ориентированный граф - граф в котором пары вершин в ребрах...
-
Некоторые сведения из теории графов - Алгоритмы нескольких махов
Приведенные ниже определения взяты из [1,2,7-9], теоремы из [6]. Граф, или обыкновенный граф G -- это упорядоченная пара G := (V, E), где V -- это...
-
Введение - Определение кратчайшего пути в графе
Начало теории графов как математической дисциплины было положено Эйлером в его знаменитом рассуждение о Кенигсбергских мостах. Однако эта статья Эйлера...
-
Кратко напомним некоторые фундаментальные определения и теоремы линейной алгебры и выпуклого анализа, которые широко применяются при решении проблем как...
-
Понятие матрицы Матрицей А размером mn или просто (mn)-матрицей называют прямоугольную таблицу, содержащую m строк и n столбцов, элементами которой...
-
Основные термины теории баз данных - БД (База данных) - совокупность специальным образом организованных данных, хранимых в памяти вычислительной системы...
-
Силовые алгоритмы для иерархически-кластеризованных графов - Визуализация графа цитирования
На данный момент мы рассмотрели алгоритм для отрисовки некластеризованных графов и их улучшения. Теперь необходимо изучить подходы, которые используются...
-
Автоматическое расположение вершин на плоскости - Визуализация графа цитирования
Первая проблема, о которой стоит поговорить - это проблема автоматического расположения вершин на плоскости. Для начала поставим базовую задачу, как она...
-
Для проведения тестов была написана программа задания единичного интервального графа. Входные параметры: число вершин, длина отрезка на котором задается...
-
Перед написанием основных алгоритмов были разработаны модули-классы, отвечающие за геометрические примитивы. Так как визуализация производится в...
-
Основные понятия и определения Прежде чем приступить к обсуждению вопросов оптимизации, введем ряд определений и рассмотрим основные понятия. Оптимизация...
-
ОСНОВНЫЕ ПОЛОЖЕНИЯ, ОПРЕДЕЛЕНИЯ И ПОНЯТИЯ Совокупность управляющих воздействий, направленных на то, чтобы действительный ход процесса соответствовал...
-
Элементы теории графов. Сеть Петри. Конечный автомат
Вариант №8 Задача 1. Элементы теории графов Связный ориентированный граф G(Х, Г) задан множеством вершин X={x1, x2, ..., xn} и отображением Гxi={x|Ik|,...
-
Степени матриц Произведение матриц AAA...A, где A - квадратная матрица порядка n, можно записать в виде Ak, где k означает число сомножителей, входящих в...
-
Функции СУБД: 1. ведение БД: ввод, корректир, сортировка, обработка, поиск данных, обработка по запросу. 2. обеспечение безопасности и целостности данных...
-
Автоматическая расстановка вершин на плоскости Для автоматической расстановки вершин использовался алгоритм основанный на работах Eades [9],...
-
Реализация визуализации анимации алгоритма - Визуализация графа цитирования
При работе алгоритма расположения вершин графа необходимо анимировать изменения графа в режиме реального времени. Для этого используется специальная...
-
Существующие решения - Визуализация графа цитирования
На данный момент не было найдено решений, которые полностью бы удовлетворяли всем требованиям, однако существуют те, которые реализуют их не все и/или не...
-
Программные модули проекта, Представление графа в памяти ЭВМ - Алгоритмы нескольких махов
Все программы были реализованы на языке С++ на персональной ЭВМ с операционной системой Windows. Каждая программа представляет собой консольное...
-
Основные сведения о коде - Построение декодера Рида - Маллера
За время исследования помехоустойчивых кодов была наработана огромная теория и выстроена сложнейшая математическая база помехоустойчивого кодирования....
-
Алгоритма LBFS+ достаточно для трехмахового алгоритма распознавания единичных интервальных графов, но для случая интервальных графов необходимы...
-
Из универсальных языков программирования сегодня наиболее популярны следующие: Бейсик (Basic), Паскаль (Pascal), Си++ (C++), Ява (Java). Для каждого из...
-
Визуализация кластерной структуры. Bubble Sets - Визуализация графа цитирования
Для визуализации кластерной структуры был выбран алгоритм Bubble Sets [18]. Это гибкий алгоритм, относящийся к оверлеям, основанным на областях...
-
Отображения и их свойства. Пусть X и Y - некоторые множества и ГXY, причем Пр1Г=X. Тройка множеств (X, Y, Г) определяет некоторое соответствие,...
-
Если бесконечное множество оказывается возможным привести во взаимно однозначное соответствие с натуральным рядом чисел, то такое множество называют...
-
Итерационные алгоритмы разрезания графа на куски
Лекция Итерационные алгоритмы разрезания графа на куски Суть Итерационных Алгоритмов Разрезания Графов заключается в выборе первого случайного разрезания...
-
Программа задания случайных графов Эрдеша - Реньи - Алгоритмы нескольких махов
Программа реализует алгоритм задания случайных графов Эрдеша - Реньи. В качестве входных параметров задаются число вершин и число ребер. Вершины ребер...
-
ОСНОВНЫЕ ПРОГРАММЫ АРХИВАТОРЫ И ИХ ФУНКЦИИ - Архивация информации и программы-архиваторы
Назначение программ-архиваторов заключается в экономии места на диске за счет сжатия (упаковки) одного или нескольких файлов в архивный файл....
-
Построение аналитической модели АОУ затруднено из-за отсутствия или недостатка априорной информации об объекте управления, а также из-за ограниченности и...
-
Е-здравоохранение: основные термины, понятия и заинтересованные стороны Информационные технологии (ИТ) термин, который используется в различных вариантах...
-
Определение методов реинжиниринга информационных систем Основные задачи, которые стоят перед проектировщиком, занимающимся реинжинирингом информационных...
-
Смысл таблицы - отображение строк и столбцов. Одинаковый тип данных по столбцам. Полосы прокрутки как по вертикали так и по горизонтали. Перемещение...
-
Компьютерные преступления - Основные термины по информатике
QFC - компьютерные мошенничества, связанные с хищением наличных денег из банкоматов. QFF - компьютерные подделки: мошенничества и хищения из компьютерных...
-
1. Провести обзор методов автоматического построения профиля нормального поведения веб-приложения. 2. Сформулировать требования к методу, провести...
-
Предисловие, Теория "Основные понятия Visual Basic" - Visual Basic. Основы программирования
Язык программирования Visual Basic все шире используется в российском образовании. Одна из проблем, с которыми сталкивается преподаватель, работающий с...
-
Экологическая часть, Термины и определения - Искусственный интеллект
Cтандарт ГОСТ Р 54148-2010 - "Воздействие на человека электромагнитных полей от бытовых аналогичных электрических приборов. Методы оценки и измерений"...
-
Один из наиболее простых и, в то же время, наиболее выразительных способов изменения внешнего вида текста состоит в изменении шрифта, которым он написан....
-
Задачи информатики:, Виды программ - Основные термины по информатике
* исследование информационных процессов * разработка технологий передачи информации * решение инженерных и научных проблем, внедрение во все общественные...
-
Программное обеспечение. - Основные термины по информатике
Компьютер - электронное устройство для обработки информации. Составные части компьютера называются его Аппаратным обеспечением . Совокупность...
1.2 Основные термины и теоремы теории графов - Определение кратчайшего пути в графе