Урок по теме "Графы. Цепи и Циклы"

ПУТИ в ГРАФЕ Связные графы

Теория

И

Решение задач

Составители : Хитькова И.К.

Гунина Д.А.

Обсудим… био граф ия – жизнеописание, гео граф ия – землеописание, граф ит – стержень для письма и так далее. Все эти слова имеют один корень: « граф », который проходит от греческого слова  grapho  – писать.

Графы – математические объекты, с их помощью можно решать много различных, внешне не похожих друг на друга задач.

Граф  состоит из точек и соединяющих их линий.

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

Сколько вершин и рёбер у графа,

представленного на рисунке?

Применение графов

Цепь и цикл

Цепь (простой путь) – это путь в графе из одной вершины в другую, в котором ребра и вершины не повторяются.

Если граф состоит из одной цепи, то его тоже называют цепью. Граф из одной вершины без рёбер также считают цепью.

Цикл в графе – замкнутый путь с началом и концом в одной вершине.

Задание 1. На рисунке изображен граф. Назовите всевозможные пути из вершины А в вершину Е.

Задание 2. Назовите два цикла в графе из Задания 1

Задание 3. На рисунке представлен граф. Назовите возможные пути: 1) из вершины A в вершину D. 2) Из вершины A в вершину G

Ответ :

• ___________________________

• ___________________________

Граф называется связным , если две любые вершины в этом графе соединены путём. Граф из Задания 1 – связный Граф из Задания 3 – несвязный .

• Задание 4 . На рисунке представлены графы. Определите связные ли они:

1)

2)

3)

4)

Связный граф

Несвязный граф

Задание 5. На рисунке представлены графы. Укажите графы, которые содержат цикл:

Ответ: ________________

_____________________________________________________________________

3)

1)

2)

6)

4)

5)

7)

8)

10)

9)

Решите задачу и составьте граф самостоятельно

Космическая федерация управляет маршрутами между планетами Солнечной системы и планетами соседней Альфа-системы. Ракеты летают между некоторыми парами планет, образуя сложную сеть. писок маршрутов между планетами (двусторонние):

В Солнечной системе: Земля–Меркурий, Венера–Марс, Меркурий – Юпитер, Юпитер–Сатурн, Уран–Нептун, Сатурн-Плутон, Нептун–Плутон;

Между звездными системами: Плутон–Альфа−1,Марс–Альфа−2;

В Альфа-системе: Альфа−1–Альфа−2, Альфа−2–Альфа−4, Альфа−4–Альфа−5.

Можно ли добраться с Земли до Альфа-5? Напишите этот путь.

• Указание: Для решения этой задачи составьте граф, соединив рёбрами планеты в Солнечной системе и системе Альфа.

• Задание 7. Изобразите какой-нибудь граф, у которого:

• 4 различных цикла
• 3 цикла длин 3, 4, 5.

Задание 8. Изобразите 2 графа с восемью вершинами степени 2. Один связный, другой - несвязный

Спасибо за урок!