Презентация, доклад на тему Графы

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

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

в одном из своих писем он формулирует и предлагает решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов.

графа, имеющая нечётную степень, называется нечетной, а чётную степень – чётной.

Нечётная степень

Чётная степень

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

конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей. Вершины v0, vn называются связанными данным путем (или просто связанными). Вершину v0 называют началом, vn - концом пути. Если v0 = vn, то путь называют замкнутым. Число n называется длиной пути.
Маршрут в графе путь, ориентацией дуг которого можно пренебречь. Маршрут, в котором все вершины попарно различны, называют простой цепью.
Цепь маршрут, в котором все ребра попарно различны.
Цикл замкнутый маршрут, являющийся цепью. Цикл, в котором все вершины, кроме первой и последней, попарно различны, называются простым циклом.

при изображении различных иерархий. Например, популярны генеалогические деревья.
Граф без цикла называется лесом. Вершины степени 1 в дереве называются листьями.  Деревья - очень удобный инструмент представления информации самого разного вида.  Деревья отличаются от простых графов тем, что при обходе дерева невозможны циклы. Это делает графы очень удобной формой организации данных для различных алгоритмов. Таким образом, понятия дерева активно используется в информатике и программировании.

Основные понятия

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

Задача 1

и слесарь занимаются боксом,
Электрик-младший из друзей.
По вечерам Андрей и токарь играют в домино против Сергея и электрика.
Определите профессию каждого из друзей.

Задача 2