Графы. Основные определения с примерами. Граф icon

Графы. Основные определения с примерами. Граф


1 чел. помогло.
Смотрите также:
Основные результаты научных исследований математические науки...
Лекция Основные определения теории цепей. Модели элементов...
Правила оформления заявки (документов и материалов), представляемой на регистрацию...
Правила оформления заявки (документов и материалов), представляемой на регистрацию...
Правила оформления заявки (документов и материалов), представляемой на регистрацию...
Надежность в технике основные понятия. Термины и определения гост 27...
Рабочая программа дисциплины Графы и алгоритмы Направление подготовки...
Основы метрологии стандартизации и сертификации...
«Действиям»
Тематическое планирование по литературному чтению 2 класс...
«Вентана-Граф»...
«Коллоидная химия» Лекция 1 Основные определения коллоидной химии и ее предмета...



Загрузка...
скачать
Графы. Основные определения с примерами.


Граф – это некоторое конечное множество точек, называемых вершинами, и конечный набор линий, называемых ребрами, соединяющих некоторые пары точек из .

Пример: схема автомобильных дорог, связывающих города некоторой области, является характерным примером графа.


Ориентированный граф (орграф) – это граф, у которого пары в наборе X являются упорядоченными.

Пример: пусть , .

Тогда – ориентированный граф.


Дуга – это направленное ребро в орграфе.

Пример: в приведенном выше примере для орграфа дугами являются ребра , , .


^ Начальная вершина – вершина орграфа, которой инцидентны только исходящие дуги.

Пример: пусть – ориентированный граф, , , тогда – начальная вершина.


^ Конечная вершина – вершина орграфа, которой инцидентны только заходящие дуги.

Пример: пусть – ориентированный граф, , , тогда – конечная вершина.


Петля – ребро графа, инцидентное единственной вершине.

Пример: пусть – ориентированный граф, ,

, тогда , , – петли.


Изолированная вершина – вершина, которая не имеет инцидентных ребер.

Пример: пусть – ориентированный граф, , , тогда , – изолированные вершины.


Степень вершины – число инцидентных ребер, .

Пример: пусть – граф, изображенный на рисунке. Тогда , , – соответственно степени вершин , , .


Псевдограф – граф с кратными ребрами и петлями.

Пример: пусть – ориентированный граф, , .

Тогда – ориентированный псевдограф.


Пустой граф – граф , в котором .

Пример: пусть – граф, изображенный на рисунке. Он является пустым, т.к. ,


Полный граф – граф , в котором любая пара вершин инцидентна единственному ребру. Обозначается , где , при этом .

Пример: приведенный на рисунке граф является полным, т.к. это видно из определения и , при этом выполняется .


Мультиграф – граф, в котором имеются кратные (параллельные) ребра.

Мультиграф – это псевдограф без петель.

Пример: пусть – ориентированный граф, , . Тогда – ориентированный мультиграф.


^ Однородный граф – граф, все вершины которого имеют одну и ту же степень.

Пример: следующие графы, приведенные на рисунке, являются однородными со степенью вершин . (рис. (а) и (б))




Матрица смежности – квадратная матрица является матрицей смежности графа , если при в графе вершины и соединены ребрами, при вершины и в несмежны.

Пример: для орграфа , изображенного на рисунке, приведем матрицу смежности:


Матрица инцидентности орграфа – прямоугольная матрица , ,если вершина является началом дуги ; , если вершина является концом дуги ; , если вершина не инцидентна дуге .

Пример: для орграфа, приведенного в примере для матрицы смежности, составим матрицу инцидентности:


Два графа и являются изоморфными, если между парами множеств их вершин, ребер и дуг существуют взаимно однозначные соответствия, сохраняющие смежность и ориентацию для дуг.

Пример: следующие графы, приведенные на рисунке, изоморфны:


Маршрут длины H – чередующаяся последовательность вершин и ребер , обладающих тем свойством, что пара соседних элементов инцидентна.

Пример: последовательность – маршрут длины 3, соединяющий вершины и в графе, приведенном на рисунке.


Замкнутый маршрут – маршрут, у которого начальная вершина совпадает с конечной.

Пример: пусть – граф, показанный на рисунке, тогда – замкнутый маршрут длины 4.


Цепь – маршрут, в котором все ребра различны.

Пример: пусть – ориентированный граф, приведенный на рисунке. Тогда – цепь из в длины 3.


Простая цепь – цепь, в которой все вершины различны.

Пример: для ориентированного графа , приведенного выше в примере с цепью, и – простые цепи из в длины 2.


Цикл – цепь, у которой начальная и конечная вершина совпадают.

Пример: пусть – граф, показанный на рисунке, тогда – цикл.


Простой цикл – простая цепь, у которой концевые вершины совпадают.

Пример: пусть – граф, показанный на рисунке, тогда – простой цикл.


Эйлеров цикл – это цепь, содержащая все ребра графа в точности один раз, у которой начальная и конечная вершина совпадают.

Пример: пусть – граф, показанный на рисунке, тогда существует Эйлеров цикл – .


Гамильтонов цикл – это простая цепь, содержащая все вершины графа, у которой начальная и конечная вершины совпадают.

Пример: приведенный на рисунке граф имеет Гамильтонов цикл: .


Путь (ориентированная цепь) – цепь орграфа . в которой ориентация дуг (ребер) совпадает.

Пример: для ориентированного графа, приведенного на рисунке, имеем путь из в длины 3: .


^ Простой путь – путь, не содержащий повторяющихся вершин.

Пример: для ориентированного графа, приведенного на рисунке, имеем простой путь из в : .


Контур – путь, у которого начальная и конечная вершины совпадают.

Пример: для ориентированного графа, приведенного на рисунке, имеем контур:


^ Простой контур – контур, не содержащий повторяющихся вершин.

Пример: для ориентированного графа, изображенного на рисунке, имеем простой контур: .


Подграф графа – граф , для которого и две вершины в смежны тогда и только тогда, когда они смежны в .

Пример: пусть – исходный граф, показанный на рисунке (а), тогда – некоторый подграф графа (рисунок (б)).





Суграф графа – граф содержит то же множество вершин, что и сам граф и .

Пример: пусть – некоторый исходный граф, показанный на рисунке (а), тогда – некоторый суграф графа (б).


^ Связный граф – граф, у которого любая пара вершин взаимодостижима.

Пример: оба графа, которые были приведены выше в качестве примеров суграфа, являются также связанными графами.


^ Сильносвязный граф – орграф, у которого любые две вершины взаимодостижимы.

Пример: следующие два ориентированных графа, показанных на рисунке, являются сильносвязанными орграфами.


Компонента связности графа – максимальный подграф графа , в котором все вершины попарно достижимы.

Пример: у графа, показанного на рисунке, три компоненты связности.


Сильная компонента орграфа – максимальный подграф орграфа , в котором любая пара вершин сильно связана.

Пример: у орграфа, изображенного на рисунке, три компоненты сильной связности.


Вершина ориентированного графа называется достижимой из вершины , если существует путь с началом в и концом в .

Пример: в приведенном на рисунке орграфе вершина является достижимой из вершины .


Минимальная длина простой цепи с началом в и концом в называется расстоянием между этими вершинами.

Пример: в графе, изображенном на рисунке, расстояние между вершинами и равно трем.


^ Смешанный граф – это граф, содержащий как дуги, так и ненаправленные ребра.

Пример: граф, показанный на рисунке, является смешанным.


Вершина инцидентна дуге тогда и только тогда, когда является либо началом, либо концом дуги .

Пример: на рисунке вершины и инцидентны дуге .


^ Отношение смежности:

Две вершины смежны в графе тогда и только тогда, когда существует ребро графа, инцидентное им обоим. Два ребра смежны в графе тогда и только тогда, когда существует, по крайней мере, одна вершина, инцидентная им обоим.

Пример: вершины и смежны, т.к. существует ребро x, инцидентное им обоим (рис (а)). Ребра и смежны, т.к. существует вершина , инцидентная им обоим (рис (б)).


Обыкновенный граф – неориентированный граф, который не содержит параллельных ребер и петель; орграф, который не содержит строго параллельных дуг и петель.

Пример: на рисунке изображен обыкновенный граф .


Обозначим через k-ю степень матрицы смежности орграфа . Тогда элемент матрицы ориентированного псевдографа , где , равен числу всех путей длины из в .

Пример: существует один путь из в длины 2.




Граф называется деревом, если он является связным и не имеет циклов. Число ребер такого графа равно на единицу меньше числа его вершин.

Пример: граф , изображенный на рисунке, является деревом. Из рисунка видно, что выполняется соотношение (в нашем случае).


Список используемой литературы:

  1. В. Н. Нефёдов, В. А. Осипова: "Курс дискретной математики", 1992 г.

  2. М. И. Нечепуренко: "Алгоритмы и программы решения задач на графах и сетях", 1990 г.

  3. Р. Басакер, Т. Саати: "Конечные графы и сети", 1974 г.

  4. В. В. Белов, Е. М. Воробьёв, В. Е. Шаталов: "Теория графов", 1976 г.

  5. О. П. Кузнецов, Г. М. Адельсон - Вельский: "Дискретная математика для инженера", 1988 г.




Скачать 92,02 Kb.
оставить комментарий
Дата29.09.2012
Размер92,02 Kb.
ТипДокументы, Образовательные материалы
Добавить документ в свой блог или на сайт

отлично
  3
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Загрузка...
Документы

Рейтинг@Mail.ru
наверх