Основные понятия теории графов

Графы. Вершина. Ребро. Представление задачи с помощью графов.

Леонард Эйлер

(1707г – 1783гг)

Швейцарский, прусский и российский математик

Теория графов зародилась в ходе решения головоломок двести с лишним лет назад.

Основы теории графов как математической науки заложил в 1736 г. Леонард Эйлер, рассматривая задачу о кенигсбергских мостах. Сегодня эта задача стала классической.

Итак, как вы все знаете, 1ая работа по теории графов принадлежит Леонарду Эйлеру. Ещё в 1736 году в одном из своих писем итальянскому математику и инженеру Мариони он формулирует и предлагает решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов. Но при решении этой задачи сам Эйлер не использует термин «граф». Только через 200 лет, в 1936 году, этот термин был предложен венгерским математиком Денешом Кёнигом в его работе «Теории конечных и бесконечных графов». В начале 20 века наряду с термином «граф» употреблялись и другие: карта, комплекс, диаграмма, сеть, лабиринт и т.п. В настоящее время, термин «граф» считается устоявшимся, хотя в прикладной математике, наряду с ним употребляется и термин «сеть» (сети Петри, нейронные сети и т.д.)

Слово « граф » в математике означает картинку, где нарисовано несколько точек, некоторые из которых соединены линиями. В процессе решения задач математики заметили, что удобно изображать объекты точками, а отношения между ними отрезками или дугами.

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

Графом называется конечное множество точек, некоторые из которых соединены линиями.

Точки называются вершинами графа, а соединяющие линии – рёбрами .

(Каждое ребро соединяет ровно две вершины).

Рёбра графа

Вершины графа

Примеры различных графов

Определение.

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

Пример.

Вершина 5 является

изолированной.

Задание.

Вершины графа представляют жителей городка N, а ребра, соединяющие две вершины, - тот факт, что эти люди знакомы. Какую ситуацию изображает приведенный на рисунке граф?

Определение.

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

Пример

Вершины А и Б - висячие.

Задание

Укажите висячие вершины.

Есть ли здесь изолированные вершины?

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

Задание 1. Начертите граф, содержащий четыре висячих и две изолированные вершины. Задание 2. Начертите граф, содержащий шесть висячих и три изолированные вершины.

Задание 3 . Сколько ребер и вершин в графе? Укажите висячие вершины. Есть ли здесь изолированные вершины?

а)

б)

D

F

B

C

E

A

. R

G

H

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

Задание 1. Начертите граф, содержащий пять висячих и четыре изолированные вершины. Задание 2. Начертите граф, содержащий две висячих и пять изолированные вершины.

Задание 3 . Сколько ребер и вершин в графе? Укажите висячие вершины. Есть ли здесь изолированные вершины?