Теория Графоведения

Министерство образования и  науки РФ.

ФГБОУ «Восточно-Сибирский Государственный Университет Технологии и Управления».

Кафедра: «Высшая Математика».

 

 

 

 

 

 

 

РЕФЕРАТ: «Теория графов».

 

 

 

 

 

 

 

Выполнил: ст. Б-421-2 Мисайлов А.С.

Проверил (а): Назарова Л.И.

 

 

 

 

 

Г.Улан-Удэ.

2013 г.

Содержание:

 

1. История Т.Г.

 

 

2. Основная суть Т.Г.

 

 

3. Законы. Формулы.

 

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

История Теории Графов.

Начало Теории Графов положило в 1736 году Леонардо Эйлером задача о Кенигсбергских мостах.

Эйлер показал, что эта задача не имеет решение т. К. нельзя построить замкнутый маршрут вдоль рёбер графа.

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

Впервые термин «граф» был введён на рассмотрение венгерским математиком  Кернингом в 1903 году.

 

 

 

Основные определения.

Под графом (G) будем понимать пару множеств V, E.

V - Множество вершин.

E – Множество рёбер.

G= (V, E)

Порядком графа называют (V) – число элемента множества V.

Если граф содержит n-вершин и m рёбер, то его будем называть (n,m)-граф.

Две вершины U₁ и U₂ называют смежными, если в графе существует ребро соединяющие эти вершины. E_I= U₁U_E – ребро графа с кольцевыми концами U_K и U_E. При этом говорим, что L_I инцидентно вершинам U_K и U_E, а вершины U_K и U_E инцидентны ребру E_I.

Граф называют полным, если любые  две вершины смежные.

Полный граф порядка (степени) n – k_n.

При: K₃

Степенью вершины d(U) называют число инцидентных ей рёбер.

Если каждое ребро графа имеет  ориентацию, то говорят об ориентированном  графе (орграф).

Для орграфа вводят в рассмотрение степени исхода и захода вершин.

Цепи, циклы и компоненты.

Маршрутом, соединяющим вершины U и U_L+1 (U, U_L+1) – называют последовательность: U₁, l₁,U₂,l₂,…,U_I,L_L,U_E+1     (1)

Вершин и рёбер графа, где  L_i=V_iU_l+1, I= 1,e.

Маршрут называют цепью, если все его рёбра различны и простой цепью, если все его вершины кроме возможно крайних различны.

Маршрут (1) называют циклическим, если U₁=U_L+1.

Циклическая цепь называется циклом.

Циклическая простая цепь - простым  циклом.

Число рёбер в маршруте называют его длиной, простой цикл длины  L будем называть L-циклом. Обхват графа – это минимальное из длин циклов графа.

Вершина U называется достижимой из вершины V, если в графе существует UV- маршрут. Граф называют связным, если любые его две несовпадающие вершины соединены маршрутом.

 

 

 

 

 

 

 

 

 

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

 

1)Восстановленные лекции студентов  Б-421 группы (Техмаш).

2)Википедия.