Презентация на тему Графы

которых соединены ребрами т.е. это совокупность точек, называемых вершинами,

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

соединены только одним ребром. Соединяющие линии называются ребрами.
(смежные вершины

– это 2 вершины, соединенные ребром)

линиях, соединяющих вершины, указано направление (соединяющие линии называются дугами)

каждого ребра проставлено число, характеризующее связь между соответствующими вершинами

(граф с помеченными ребрами).

проставлено число, характеризующее связь между соответствующими вершинами (орграф с

помеченными ребрами).

или сетью, сводится, как правило, к нахождению оптимального в

том или ином смысле маршрута, ведущего от одной вершины к другой

около каждого ребра проставлено не число, а иная информация,

характеризующее связь между соответствующими вершинами.

ребра)

выходящих из одной вершины

удвоенному количеству ребер
2) Для любого графа количество вершин нечетной

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

в которой конец одного ребра служит началом следующего (циклический

маршрут – если конец последнего ребра последовательности совпадает с началом 1-го ребра) 2) Цепь – это маршрут, в котором каждое ребро содержится не более одного раза 3) Цикл – это цепь, являющаяся циклическим маршрутом 4) Простая цепь – это цепь, проходящая через каждую свою вершину ровно 1 раз 5) Простой цикл – это цикл, являющийся простой цепью 6) Связанные вершины – это вершины (например, А и B), для которых существует цепь, начинающаяся в А и заканчивающаяся в B 7) Связный граф – это граф, у которого любые 2 вершины связанны. Если граф несвязен, то в нем можно выделить так называемые связанные компоненты (т.е. множества вершин, соединенных ребрами исходного графа, каждое из которых является связным графом) Один и тот же граф может быть изображен по-разному.

перечисленных ниже случаев изобразите граф и определите все степени

вершин
а) вершины x y соединены ребром тогда и только тогда, когда (x-y)/3 целое число
б) вершины x y соединены ребром тогда и только тогда, когда x+y=9
в) вершины x y соединены ребром тогда и только тогда, когда x+y содержится в множестве V={1,2,3,4,5,6,7,8,9,10}
г) вершины x y соединены ребром тогда и только тогда, когда |x-y|<3 (выполнить самостоятельно)
д) вершины x y соединены ребром тогда и только тогда, когда x y не взаимно просты (выполнить самостоятельно)

государстве, в котором из каждого города выходят ровно 3

дороги, быть ровно 100 дорог?
Ответ: Нет (по формуле 3n=2*100, откуда n-количество городов- не целое)
2) – Наша шпионская сеть была хорошо законспирирована, - признался на допросе агент 007. – В ней было 77 агентов, но каждый знал только семерых. Почему наверняка можно утверждать, что агент врет?
Ответ: По условию задачи 7*77=2*n, откуда n - не целое.

табличное представление:

К.
1 СПОСОБ РЕШЕНИЯ:
РУЧНОЙ (ВРУЧНУЮ СЧИТАЕМ КОЛИЧЕСТВО ПУТЕЙ

ИЗ А В К)

ОТВЕТ: 17

2 СПОСОБ РЕШЕНИЯ:
ПОСТРОЕНИЕ ДЕРЕВА РЕШЕНИЯ

ОТВЕТ: 17