Ihgkjfioklmgtk;., fv

  • 16 дек. 2012 г.
  • 1494 Слова
БОУ Чувашской Республики СПО «Чебоксарский Электромеханический колледж»

Реферат
по дисциплине «Математика»
на тему: Основные понятия теории графов



Выполнили: студентки группы Км1-11
Антонова Надежда, Гордеева АнастасияРуководитель: Киреева Н.В.

Чебоксары 2012
Содержание:
Введение
1.Графы. Основные определения.
2.Элементы графов
3.Виды графов и операции над ними
4.Заключение
5.Использованная литература

Введение


1.Графы. Основные определения.
Графом называется совокупностьконечного числа точек, называемых вершинами графа, и попарно соединяющих некоторые из этих вершин линий, называемых ребрами или дугами графа.
Это определение можно сформулировать иначе: графом называется непустое множество точек (вершин) и отрезков (ребер), оба конца которых принадлежат заданному множеству точек.
Пример: схема автомобильных дорог, связывающих города некоторой области, является характернымпримером графа.

Ориентированный граф (орграф) – это граф, у которого пары в наборе X являются упорядоченными.
Пример: пусть V=(V₁, V₂,V₃), X=(x₁=(V₁,V₂), x₂=(V₂,V₁), x₃=(V₂,V₃)) .
ТогдаD=(V,X) – ориентированный граф.

Дуга – это направленное ребро в орграфе.
Пример: в приведенном выше примере для орграфаD=(V,X) дугами являются ребра x₁, x₂, x₃.
Начальная вершина – вершина орграфа, которойинцидентны только исходящие дуги.
Пример: пустьD=(V,X) – ориентированный графV=(V₁,V₂,V₃), X=(x₁=(V₁,V₂), x₂=(V₁,V₃)) , тогда V₁– начальная вершина.

Конечная вершина– вершина орграфа, которой инцидентны только заходящие дуги.
Пример: пустьD=(V,X) – ориентированный граф V=(V₁,V₂,V₃), X=(x₁=(V₂,V₁), x₂=(V₃,V₁)), тогдаV₁– конечная вершина.

Петля – ребро графа, инцидентное единственнойвершине.
Пример: пусть D=(V,X) – ориентированный граф V=(V₁,V₂,V₃), X=(x₁=(V₁,V₁), x₂=(V₁,V₂), x₃=(V₂,V₂), x₄=(V₁,V₃), x₅=(V₃,V₃)), тогда x₁, x₃, x₅ – петли.

Изолированная вершина – вершина, которая не имеет инцидентных ребер.
Пример: пусть D=(V,X) – ориентированный граф V=(V₁,V₂,V₃,V₄), X=(x₁=(V₂,V₃), x₂=(V₃,V₂)) тогда V₁, V₄ – изолированные вершины.
-
Степень вершины – число инцидентных ребер, S(X).Пример: пусть G=(X,R) – граф, изображенный на рисунке. ТогдаS(x₁)=2, S(x₂)=1, S(x₃)=1 – соответственно степени вершин x₁, x₂, x₃.
Однородный граф – граф, все вершины которого имеют одну и ту же степень.
Пример: следующие графы, приведенные на рисунке, являются однородными со степенью вершин S(X)=2 . (рис. (а) и (б))

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

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

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

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

Обыкновенный граф – неориентированный граф, который не содержит параллельных ребери петель; орграф, который не содержит строго параллельных дуг и петель.
Пример: на рисунке изображен обыкновенный граф G=(V,X).

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

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