Презентация по информатике на тему "графы" (9 класс)

ПОНЯТИЕ “ГРАФ” В ИНФОРМАТИКЕ

Теория графов (математика)

■    В самом общем смысле граф — это множество точек (вершин, узлов), которые соединяются множеством линий (рёбер, дуг).

■    Раздел математики, изучающий теорию графов, называется ДИСКРЕТНОЙ МАТЕМАТИКОЙ.

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

■    Теория графов (то есть систем линий, соединяющих заданные точки) включена в учебные программы для начинающих математиков, поскольку

                     ■   как и геометрия, обладает наглядностью;

                     ■        как и теория чисел, проста в объяснении и имеет сложные нерешённые задачи;

■  не имеет громоздкого математического аппарата («комбинаторные методы нахождения нужного упорядочения объектов существенно отличаются от классических методов анализа поведения систем с помощью уравнений»); ■ имеет выраженный прикладной характер.

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

■    Теория графов, как математическое орудие, приложима как к наукам о поведении (теории информации, кибернетике, теории игр, теории систем, транспортным сетям), так и к чисто абстрактным дисциплинам (теории множеств, теории матриц, теории групп и так далее).

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

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

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

— Леонард Эйлер. Решение одной задачи, связанной с геометрией положения

Решение задачи по Эйлеру

■          На современном языке это означает, что схеме мостов города соответствует граф, представляющий собой:

■  четыре вершины A,B,C,D по обозначениям четырёх частей центра города;

■             вершины соединены семью рёбрами-мостами a,b,c,d,e,f,g по обозначениям семи мостов.

■      Достаточно современное и простое решение Леонардом Эйлером задачи о кёнигсбергских мостах выглядит следующим образом. Только следует иметь ввиду, что Эйлер современной терминологии не знал, термин «граф» не использовал, называл ребро «мостом», а вершину — «областью» или «буквой» и не рисовал современные изображения графов.

■      «Таким образом, становится очевидным, что если можно пройти по семи мостам, причём по каждому из них ровно по одному разу, то этот маршрут будет изображаться восемью буквами».

■      «…я разработал правило, по которому можно легко решить — как для этой задачи, так и для всех подобных задач, — может ли быть осуществлено такое расположение букв.

■    « Чтобы вывести подобное правило, я рассматриваю некоторую конкретную A, в которую может вести произвольное число мостов a,b,c,d и т. д. Из этих мостов сначала я рассмотрю конкретный мост a, ведущий в A. Если путешественник пройдёт по этому мосту, то он либо находился в области A до того, как прошёл по этому мосту, либо окажется в области A после этого. Поэтому чтобы обозначить этот проход по мосту, как описано выше, необходимо, чтобы один раз возникла буква A

■    «Если в область A ведут три моста, например a,b,c, и путешественник проходит по всем трём мостам, то буква A будет встречаться в описании его движения по мостам дважды независимо от того, начинался его маршрут из  A или нет. Точно так же, если в область A ведут пять мостов, то буква A должна встретиться при описании его движения три раза. И когда количество мостов — произвольное нечётное число, то если увеличить его на единицу, половина полученного числа показывает, сколько раз должна встретиться буква

A.»

■    « Следовательно, в случае с кёнигсбергскими мостами, поскольку на остров A ведут пять мостов a,b,c,d,e, необходимо, чтобы буква Aвстретилась в описании движения по этим мостам трижды. Кроме того, дважды должна встретиться буква B, так как в область B ведут три моста, и буквы D,C должны встретиться по два раза каждая. Поэтому в последовательности из восьми букв, с помощью которой описывается рассматриваемый маршрут, проходящий через семь мостов, буква A должна встретиться три раза, а каждая из букв B,C,D — по два раза. Такого, однако, в последовательности из восьми букв быть не может. Таким образом, ясно, что подобная прогулка по семи мостам Кёнигсберга невозможна.»

Матрица смежности

■    Для хранения информации об узлах и связях показанного выше графа     можно использовать таблицу такого вида

Домашнее задание

■   Познакомиться со следующими понятиями:

■    Связный граф

■    Взвешенный граф

■    Оптимальный путь в графе

■    Ориентированный граф  (орграф)

■    Цикл

■    Дерево