Презентация на тему Определение графа

двести с лишним лет назад. Одной из таких задач-головоломок

Задача. В г. Кёнигсберге (ныне Калининград) было семь мостов через реку Прегель (Л - левый берег, П - правый берег, А и Б - острова). Можно ли, прогуливаясь вдоль реки, пройти по каждому мосту ровно один раз?

в котором ребра соответствуют мостам, а вершины – берегам

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

этой вершине (ребра, с началом и концом в данной

Теорема. Для уникурсального графа число вершин нечетного индекса равно нулю или двум.

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

Верно и обратное: Если у связного графа число вершин нечетного индекса равно нулю или двум, то он является уникурсальным.

графа задачи Эйлера. Вершина А имеет индекс 5, Б

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

уникурсальным, если его можно ли нарисовать «одним росчерком», т.е.

вершины графа называется число ребер, сходящихся в этой вершине

графа?
Ответ: Для уникурсального графа число вершин нечетного индекса равно

имеет индекс 3. Сколько у него ребер? Нарисуйте такой

имеет индекс 4. Сколько у него ребер? Нарисуйте такой

уникурсальными?
Ответ: а), б), г), д), ж), з).

нечетного индекса; б) две вершины нечетного индекса; в) три

Ответ: а), в) Нет; б), г) да.

кёнигсбергских мостах придется пройти дважды, чтобы пройти по каждому

Ответ: Два.

по каждому ребру ровно один раз?
Ответ: Нет.

чтобы обойти все ребра тетраэдра?
Ответ: Одно.

чтобы обойти все ребра тетраэдра и вернуться в исходную

Ответ: Два.

по каждому ребру ровно один раз?
Ответ: Нет.

чтобы обойти все ребра куба?
Ответ: Три.

чтобы обойти все ребра куба и вернуться в исходную

Ответ: Четыре.

по каждому ребру ровно один раз?
Ответ: Да.

по каждому ребру ровно один раз?
Ответ: Нет.

чтобы обойти все ребра икосаэдра?
Ответ: Пять.

чтобы обойти все ребра икосаэдра и вернуться в исходную

Ответ: Шесть.

по каждому ребру ровно один раз?
Ответ: Нет.

чтобы обойти все ребра додекаэдра?
Ответ: Девять.

чтобы обойти все ребра додекаэдра и вернуться в исходную

Ответ: Десять.