Презентация, доклад по информатике Информационное моделирование. Граф.

точно известен ее создатель, время и место создания: Леонард Эйлер, 1736 год, г. Петербург. Именно в этом году Л.Эйлером в «Записках Петербургской академии наук» была опубликована статья, в которой приводилось решение широко теперь известной задачи о Кенигсбергских мостах. В ней великий математик сформулировал и обосновал критерий, позволяющий отвечать на данный вопрос для любого графа.

этот город называется Калининград), поставил задачу (1736), известную в математике как задача о семи кенигсбергских мостах: можно ли пройти по всем этим мостам и при этом вернуться в исходную точку так, чтобы по каждому мосту пройти только один раз.

левый берег, C – правый берег, А и D – острова. Можно ли, прогуливаясь по городу, пройти через каждый мост ровно по одному разу?






Решение: Определим четность вершин графа. В вершине А сходится 5 ребер, в D – 3, в C – 3, в B – 3. Имеем 4 нечетные вершины. Следовательно, граф не является уникурсальным. Значит, нельзя пройти по всем семи мостам, побывав на каждом только один раз.

Задача о Кенигсбергских мостах

столетия. Лишь в середине XIX века возродился интерес к теории графов. Исследование электрических сетей, структур молекул и строения кристаллов, применения к решению проблем в биологии и психологии послужили мощным катализатором в становлении данного раздела математики. Графы оказались удобным средством для описания самых разнообразных систем и явились эффективным инструментом структурного анализа. Графы успешно применяются для решения разнообразных задач планирования – выбор оптимального маршрута (транспортная задача), построение сетевого графика, исследование потоков в сетях и т.п.

и существующий как единое целое (из учебника).

Система – это целое, состоящее из объектов, взаимосвязанных между собой (человек, книга, обучение в школе и т.д.).

Граф – это средство для наглядного представления состава и структуры системы.

или сети передачи данных;

2) математический объект
G = (V, E)
где V — это непустое множество вершин,
E — множество ребер (пар вершин).

стрелкой) называется дугой.
Линия ненаправленная (без стрелки) называется ребром.
Линия, выходящая из некоторой вершины и входящая в неё же, называется петлей.

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

помощью таких графов могут быть представлены схемы двухсторонних (симметричных) отношений.

Граф, отражающий отношение «переписываются» между объектами класса «дети»

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

помощью таких графов могут быть представлены схемы односторонних отношений.

Граф, отражающий отношение «пишет письма».

несут дополнительную информацию (вес).

или рёбер, то такой граф называется ВЗВЕШЕННЫМ.

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

Принцип связи – «многие ко многим».
Иерархия - это расположение частей или элементов целого в порядке от высшего к низшему.

Отношения подчиненности в школе

Дерево – граф иерархической структуры. Между любыми двумя его вершинами существует единственный путь. Дерево не содержит циклов и петель.

Классификация компьютеров

Семантическая сеть

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

Количество вершин нечетной степени любого графа всегда четно.

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

(b,c), (c,b), (a,c),(c,a),(c,d),(d,c)}
Геометрический
Матрица смежности

связи между узлами (без учета дублирования) – матрицу.

ВЕСОВАЯ МАТРИЦА

в которой конец одного ребра служит началом другого. Циклическим маршрут называется в том случае, если конец последнего ребра последовательности совпал с началом первого ребра.
Для графа, изображенном на рисунке,  a1,a2,a3,a7,a1,a5 маршрут, a6,a2,a5,a7 — циклический маршрут, а последовательность a7,a6,a2,a1,a4-маршрутом не является.

одного раза. Цепь, являющаяся циклическим маршрутом, называется циклом.

a1,a2,a6,a7,a4,a5,a7 — цепь, a2,a6,a7,a8,a4,a2,a6 — цикл.

Цепь называется простой, если проходит через каждую свою вершину ровно один раз.
Цикл называется простым, если является простой цепью.

a1,a2,a6,a7,a4 — простая цепь, a2,a6,a7,a8,a4 — простой цикл.

начинающаяся в a и заканчивающаяся в b.

Связный граф — это граф, у которого любые две вершины связанны. Если граф несвязен, то в нем можно выделить так называемые связанные компоненты (т.е. множества вершин, соединенных ребрами исходного графа, каждое из которых является связным графом).

на рисунке 1 тот же, что и изображен на рисунке 2.

Рисунок 1

Рисунок 2

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

Пятеро ученых, участвовавших в научной конференции, обменялись рукопожатиями. Сколько всего было сделано рукопожатий?

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

7 при условии, что в записи числа не должно
быть одинаковых цифр?

0

1

3

5

7

3

5

7

1

3

5

1

5

7

1

3

7

5

7

3

7

3

5

5

7

1

7

1

5

3

7

1

7

1

3

3

5

1

5

1

3

Ответ: 24 числа

Д, Е, Ж. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж?

А

Б

В

Г

Д

Ж

Е

1. А-Б-Д-Ж

3. А-Б-Г-Ж

5. А-В-Б-Г-Д-Ж

7. А-В-Г-Д-Ж

9. А-В-Ж

2. А-Б-Г-Д-Ж

4. А-В-Б-Д-Ж

6. А-В-Б-Г-Ж

8. А-В-Г-Ж

10. А-В-Е-Ж

Ответ: 10 путей

5+3+7 = 15