Презентация на тему «Элементы теории графов»

Презентация на тему: «Элементы теории графов». Автор: Showeet.com. Файл: «Элементы теории графов.pptx». Размер zip-архива: 1655 КБ.

Элементы теории графов

Выполнил: ученик 11 класса «А» Лобжа Артем

г. Комсомольск – на – Амуре, 2012 год

Элементы теории графов:

Содержание данной презентации:

Элементы теории графов:

Для начала, дадим определение термина «ГРАФ». ГРАФ - набор точек (эти точки называются ВЕРШИНАМИ), некоторые из которых объявляются смежными (или соседними). Считается, что смежные вершины соединены между собой РЕБРАМИ(или дугами). Таким образом, ребро определяется парой вершин. Два ребра, у которых есть общая вершина, также называются СМЕЖНЫМИ (или соседними) (см. схему):

Элементы теории графов:

На данной схеме вы сможете увидеть основные компоненты, из которых состоит граф:

Элементы теории графов:

На нынешний момент выделяют три основных вида графов:

Граф называется ОРИЕНТИРОВАННЫМ (или ОРГРАФОМ), если некоторые ребра имеют направление. Это означает, что в орграфе некоторая вершина может быть соединена с другой вершиной, а обратного соединения нет.

Если в графе, кроме того, допускается существование петель, т.е. ребер, соединяющих вершину саму с собой, то граф называется ПСЕВДОГРАФОМ;

Если в графе допускается существование повторяющихся ребер, то граф называется МУЛЬТИГРАФОМ;

Общие понятия теории графов:

Элементы теории графов:

Существуют всего четыре последовательности вершин в графе:

МАРШРУТ В ГРАФЕ – это последовательность соседних (смежных) вершин. Ясно, что можно определить маршрут и как последовательность смежных ребер (в этом случае ребра приобретают НАПРАВЛЕНИЕ). Заметим, что в маршруте могут повторяться вершины, но не ребра.

Общие понятия теории графов:

Элементы теории графов:

Маршрут называется ЦИКЛОМ, если в нем первая вершина совпадает с последней;

Существуют всего четыре последовательности вершин в графе:

Общие понятия теории графов:

Элементы теории графов:

ПУТЬ В ГРАФЕ (иногда говорят ПРОСТОЙ ПУТЬ) – это маршрут без повторения вершин (а значит, и ребер);

Существуют всего четыре последовательности вершин в графе:

Общие понятия теории графов:

Элементы теории графов:

КОНТУР – это цикл без повторения вершин, за исключением первой вершины, совпадающей с последней;

Существуют всего четыре последовательности вершин в графе:

Элементы теории графов:

Можно ли пройти по всем этим мостам и при этом вернуться в исходную точку так, чтобы по каждому мосту пройти только один раз?

Именно с задач, поставленных и решенных в этом разделе, началась теория графов. Философ ИММАНУИЛ КАНТ, гуляя по г. Кенигсбергу, поставил задачу (1736), известную в математике как ЗАДАЧА О СЕМИ КЕНИГСБЕРГСКИХ МОСТАХ. Знаменитый математик швейцарского происхождения ЛЕОНАРД ЭЙЛЕР блестяще решил эту задачу:

Эйлеровы и полуэйлеровы графы:

Элементы теории графов:

В соответствии с поставленной КАНТОМ (и решенной ЭЙЛЕРОМ) задачей можно дать следующие определения:

Граф (или мультиграф без петель) называется ЭЙЛЕРОВЫМ, если существует цикл без повторения ребер (такой цикл называют ЭЙЛЕРОВЫМ), обходящий все вершины графа.

Граф называется ПОЛУЭЙЛЕРОВЫМ, если существует маршрут без повторения ребер (ЭЙЛЕРОВ ПУТЬ), обходящий все ребра графа ровно один раз.

Элементы теории графов:

Кратко рассмотрим проблему, связанную с возможным обходом всех вершин в графе: существует ли в данном (СВЯЗНОМ) графе цикл (ИЛИ МАРШРУТ), обходящий каждую вершину (кроме первой) ТОЛЬКО ОДИН РАЗ?

Если такой цикл (маршрут) существует (в этом случае такой маршрут будет путем), то граф называется ПОЛУГАМИЛЬТОНОВЫМ, и соответствующий путь также называют полугамильтоновым путем.

Если такой цикл существует (в этом случае такой цикл будет контуром), то граф называется ГАМИЛЬТОНОВЫМ, и соответствующий цикл также называют гамильтоновым циклом.

Элементы теории графов:

Для начала, дадим определение термина «дерево». ДЕРЕВО - СВЯЗНЫЙ ГРАФ без контуров (а значит, и без циклов). Граф (несвязный), состоящий из нескольких деревьев иногда называют ЛЕСОМ. Напомним, что вершина в графе называется ВИСЯЧЕЙ, если ее СТЕПЕНЬ РАВНА ЕДИНИЦЕ. Дерево должно обязательно иметь висячую вершину, так как если бы степень всех вершин в дереве была бы больше или равна 2, то по самой первой лемме (Лемма №1: Если степень всех вершин в графе больше или равна двум, то граф обязательно содержит контур) граф должен иметь цикл, что противоречит определению дерева.

Элементы теории графов:

Если граф G является «деревом», то:

На данной схеме отражены основные свойства «деревьев»:

Любые две вершины в графе могут быть связаны (простым) путем, и этот путь единствен;

Число ребер (p) и число вершин в графе (q) связаны соотношением p = q – 1;