Впервые основы теории графов появились в работах Леонарда Эйлера (1707-1783; швейцарский, немецкий и российский математик) , в которых он описывал решение головоломок и математических развлекательных задач.
Теория графов началась с решения Эйлером задачи о семи мостах Кёнигсберга.
Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам (через реку Преголя), не проходя ни по одному из них дважды? Многие пытались решить эту задачу как теоретически, так и практически, во время прогулок. Но никому это не удавалось, однако не удавалось и доказать, что это даже теоретически невозможно.
Информационны
е модели.
Графы.
Впервые основы теории
графов появились в работах
Леонарда Эйлера (1707-
1783; швейцарский, немецкий
и российский математик) , в
которых он описывал
решение головоломок и
математических
развлекательных задач.
Теория графов началась с
решения Эйлером задачи о
семи мостах
Кёнигсберга.
Издавна среди жителей Кёнигсберга была
распространена такая загадка: как пройти по всем
мостам (через реку Преголя), не проходя ни по одному
из них дважды? Многие пытались решить эту задачу
как теоретически, так и практически, во время
прогулок. Но никому это не удавалось, однако не
удавалось и доказать, что это даже теоретически
невозможно.
На упрощённой схеме части
города (графе) мостам
соответствуют линии (дуги
графа), а частям города —
точки соединения линий
(вершины графа).
В ходе рассуждений Эйлер пришёл к
следующим выводам: Невозможно
пройти по всем мостам, не проходя ни
по одному из них дважды.
Задача.
Существуют 4 группы крови. При переливании крови
от одного человека к другому не все группы
совместимы. Но известно, что одинаковые группы
можно переливать от человека к человеку, т.е.
1 – 1, 2 – 2 и т.д.
А также 1 группу можно переливать всем остальным
группам,
2 и 3 группу только 4 группе.
ПЕРЕЛИВАНИЕ КРОВИ
II
I
IV
III
ГРАФЫ
Граф – это информационная
модель, представленная в
графической форме.
Граф - множество
вершин (узлов),
соединённых рёбрами.
Вершины называют
смежными, если их
соединяет ребро.
Граф с шестью
вершинами и семью
рёбрами.
Ориентированные графы -
орграфы
Каждое ребро имеет одно направление.
Такие ребра называются дугами.
Ориентированный граф
Взвешенный граф
Это граф, рёбрам или дугам которого
поставлены в соответствие числовые величины
(они могут обозначать, например, расстояние
между городами или стоимость перевозки).
Вес графа равен сумме весов его рёбер.
4
B
2 3
A
E
C
2
D
1
Таблице (она называется весовой
матрицей) соответствует граф.
Задача
Между населёнными пунктами A, B, C, D, E, F построены дороги,
протяжённость которых приведена в таблице. (Отсутствие числа в
таблице означает, что прямой дороги между пунктами нет).
Определите длину кратчайшего пути между пунктами A и F (при
условии, что передвигаться можно только по построенным дорогам).
1) 9 2) 10 3) 11 4) 12
1.
A
3.
A
5.
2
4
2
4
B
C
B
C
1
A
2
4
B
C
1
2
4
4.
1
B
C
A
7
E
2
4
B
C
1
7
4
3
E
D
3
Длина кратчайшего
маршрута A-B-C-E-F
равна 9
F
2
2.
A
E
D
E
D
3
7
4
3
7
4
3
Задача
Таблица стоимости перевозок устроена следующим образом:
числа, стоящие на пересечениях строк и столбцов таблиц,
означают стоимость проезда между соответствующими
соседними станциями. Если пересечение строки и столбца
пусто, то станции не являются соседними. Укажите
таблицу, для которой выполняется условие:
«Минимальная стоимость проезда из А в B не больше 6».
Стоимость проезда по маршруту складывается из стоимостей
проезда между соответствующими соседними станциями.
A B C D Е
A B C D Е
3 1
A
A
3 1
B
4 2
4 2
B
2
C 3 4
C 3 4
2
D 1
D 1
Е 2 2
Е 2 2
A B C D Е
A
3 1
4 2
B
2
C 3 4
D 1
2 2
Е
A B C D Е
A
3 1
4 2
B
C 3 4
2
D 1
Е 2 2
Графы. Поиск путей.
На рисунке – схема дорог, связывающих города А, Б, В, Г,
Д, Е, Ж, И, К. По каждой дороге можно двигаться только в
одном направлении, указанном стрелкой. Сколько
существует различных путей из города А в город К?
откуда?
вершина
И
Б
Д
N
А
В
Ж
К
Г
Е
А
А
АБГ
Г
БВ
ВЕ
Д
И+Д+Ж+Е=
Кол-во
путей
1
1
3
1
4
4
4
13
Б
Г
В
Е
Д
Ж
И
К
Информационные модели. Графы.pptx
