Презентация, доклад Моделирование на графах 9 кл

линий, называемых ребрами, соединяющих некоторые пары точек из.

называется ребром.

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

году Леонардом Эйлером. (>>>)


Впервые понятие «граф» ввел в 1936 году венгерский математик Денеш Кёниг.

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

поэтому вершины соединены ребрами.

Граф называется неориентированным, если его вершины соединены ребрами.

(каждый пожал руку каждому по одному разу). Сколько всего рукопожатий было сделано?

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

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

существует единственный путь. Дерево не содержит циклов и петель.

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

С, D, Е. На первом месте в цепочке стоит одна из бусин А, С, Е. На втором — любая гласная, если первая буква согласная, и любая согласная, если первая гласная. На третьем месте - одна из бусин С, D, Е, не стоящая в цепочке на первом месте. Сколько цепочек можно создать по этому правилу?

С, D, Е. На первом месте в цепочке стоит одна из бусин А, С, Е. На втором — любая гласная, если первая буква согласная, и любая согласная, если первая гласная. На третьем месте - одна из бусин С, D, Е, не стоящая в цепочке на первом месте. Сколько цепочек можно создать по этому правилу?

О

А

C

E

B

C

D

C

C

C

D

D

D

E

E

E

А

E

D

D

E

E

B

C

C

C

D

C

D

D

D

Ответ: 19

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

дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет).Определите длину кратчайшего маршрута из А в B.