Графы, 1 часть, 6 класс

Р

Г

Ы

А

Л

Э

Ф

Е

Й

0

1

_ (-3 ,5); _ (-5,5); _ (-1,5); _ (-7); _ (0);

_ (1); _ (0); _ (7); _ (  =3,14 ); _ (6).

Леонард Эйлер

(1707 – 1783)

Задача о Кенигсбергских мостах

Бывший Кенигсберг (ныне Калининград ) расположен на реке Прегель. В пределах города река омывает два острова. С берегов на острова были перекинуты мосты. Старые мосты не сохранились, но осталась карта города, где они изображены.

Дальше

Задача о Кенигсбергских мостах

Кенигсбергцы предлагали приезжим следующую задачу: пройти по всем мостам и вернуться в начальный пункт, причём на каждом мосту следовало побывать только один раз.

Дальше

Граф – это набор точек, некоторые из которых соединены линиями. Эти точки называются вершинами . Соединяющие их линии называются ребрами графа.

• 2 вершины и
• 1 ребро

• 3 вершины и
• 3 ребра
• 4 вершины и
• 5 ребер
• 6 вершин и
• 6 ребер

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

А

С

А

В

С

В

D

E

F

D

Степени вершин:

• А – 1
• В – 3
• С – 2
• D – 3
• E – 2
• F – 1
• (1+3+2+3+2+1) :2=6

Степени вершин:

• А – 1
• В – 3
• С – 2
• D - 2

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

Постройте графы:

А – 2

В – 1

С – 3

D – 4

Е - 2

А – 1

В – 3

С – 1

В

А

C

D

Е

1

2

3

5

4

Задача о Кенигсбергских мостах

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

Задача о Кенигсбергских мостах

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

Одним росчерком

Граф, который можно нарисовать, не отрывая карандаша от бумаги, называется эйлеровым .

Решая задачу О кенигсбергских мостах, Эйлер сформулировал свойства графа:

Невозможно начертить граф с нечетным числом нечетных верши н .

дальше

Одним росчерком

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

дальше

ГРАФ НАЗЫВАЕТСЯ ПОЛНЫМ , ЕСЛИ ЛЮБЫЕ ДВЕ ЕГО РАЗЛИЧНЫЕ ВЕРШИНЫ СОЕДИНЕНЫ ОДНИМ И ТОЛЬКО ОДНИМ РЕБРОМ.

ДОПОЛНЕНИЕМ ГРАФА НАЗЫВАЕТСЯ ГРАФ С ТЕМИ ЖЕ ВЕРШИНАМИ И ИМЕЮЩИЙ ТЕ И ТОЛЬКО ТЕ РЕБРА, КОТОРЫЕ НЕОБХОДИМО ДОБАВИТЬ К ИСХОДНОМУ ГРАФУ, ЧТОБЫ ОН СТАЛ ПОЛНЫМ.

ДОПОЛНЕНИЕ ГРАФА ДО ГРАФА

Алеша, Боря и Витя учатся в одном классе. Один ездит домой из школы на автобусе, другой – на трамвае, третий – на троллейбусе. Однажды после уроков Алеша пошел проводить друга до остановки автобуса. Когда мимо них проходил троллейбус, третий друг крикнул из окна: «Боря, ты забыл в школе тетрадь!» Кто на чем ездит домой?

А, Б, В и Г – друзья. Один из них – врач, другой –

журналист, третий – тренер спортивной школы и

четвертый строитель. Журналист написал статьи

об А и Г. Тренер и журналист вместе с Б ходили в

поход. А и Б были на приеме у врача. У кого какая

профессия?

В бутылке, стакане, кувшине и банке налиты молоко,

лимонад, квас и вода. Известно, что вода и молоко

находятся не в бутылке, в банке – не лимонад и не

вода, а сосуд с лимонадом стоит между кувшином

и сосудом с квасом. Стакан стоит около бутылки и

сосуда с молоком. Определите, где какая жидкость?