Теория графов

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

ФГАОУ ВПО «Северо-Восточный федеральный университет им. М.К. Аммосова»

Институт математики и информатики

Кафедра информационные технологии

ТЕОРИЯ ГРАФОВ

КОНСПЕКТ ДЛЯ СЕБЯ

(специальность:02.03.02 Фундаментальная информатика и информационные технологии. ОФО)

Выполнил: студент  1 курса

группы ФИИТ-22 ИМИ  СВФУ

Васильев Харысхан Эдуардович

Преподаватель:

(должность, уч. степень, уч. звание, Ф.И.О.)

Неустроева Татьяна Кимовна

Якутск – 2022

Оглавление

Определение графа        3

Что есть диаграмма графа?        3

Определение порядка графа. Обозначение        4

Количество различных графов n-го порядка        4

Что есть вершины и ребра графа?        5

Какой граф называют (n, m)-графом или (p, q)-графом (могут быть использованы и другие буквы)?        5

Определение инцидентности вершины и ребра графа        6

Определение изолированной вершины (через понятие инцидентности)        6

Определение смежных вершин и смежных ребер        7

Окружение вершины. Обозначение        7

Определение степени вершины. Определение висячей вершины, изолированной вершины (через понятие степени вершины)        7

Лемма о рукопожатиях и ее следствие (доказательства)        8

Определение регулярного графа степени k        9

Определение подграфа графа        9

Определение остовного подграфа        9

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

Определение ориентированного графа (орграфа). Узлы, дуги. Полустепень исхода (захода) узла орграфа        10

Определение изоморфизма двух графов. Свойства изоморфизма. Примеры инвариантов графа        11

Классы эквивалентности по отношению изоморфизма графов. Количество этих классов        12

Определение графа

[pic 1]

Пример графа:

[pic 2]

Что есть диаграмма графа?

Обычно граф представляют в виде диаграммы, и её-то часто называют графом. Диаграммы изображают в виде точек и линий, где каждой точке соответствует один элемент множества V, а для каждой линии – элемент множества E.

Те изображение, которые я использовал ранее – это диаграммы     (рис. 1.3) и те которые я буду использовать.

Определение порядка графа. Обозначение

[pic 3]

В рис 1.3 порядок равен n = 6.

Количество различных графов n-го порядка

Количество различных графов n-го порядка равна[pic 4].

Рассмотрим граф с тремя вершинами. Порядок этого графа – 3.

По формуле количество различных графов 3-го порядка: 23=8.

Если перечислить их то тоже 8(рис 2.1).

[pic 5]

Что есть вершины и ребра графа?[pic 6]

Вершина графа(v) – элемент множества V графа G.[pic 7]

Ребра графа(x) – это элемент множества E графа G,

   Пример(рис 3.1):[pic 8]

Какой граф называют (n, m)-графом или (p, q)-графом (могут быть использованы и другие буквы)?

[pic 9]

Пример: G(5, 6) (рис 5.1):

[pic 10]

Определение инцидентности вершины и ребра графа

[pic 11]

[pic 12]

Определение изолированной вершины (через понятие инцидентности)

[pic 13]

[pic 14]

Определение смежных вершин и смежных ребер

Д[pic 15][pic 16]

н

[pic 17]

Вершины A и B смежные.

Ребра g и h смежные.

Окружение вершины. Обозначение

[pic 18]

Окружение вершины D:(Рис 8.1) N(D) = {F, E, A, C}

Определение степени вершины. Определение висячей вершины, изолированной вершины (через понятие степени вершины)

Вершина графа, имеющая степень равную 1, называется висячей. То есть, это та вершина, которая соединяется только с одним ребром или дугой.[pic 19][pic 20]