Разберем задачи, подводящие, учащихся к понятию графа,
Задача 1.1.
Герой произведения Н.В.Гоголя “Мертвые души” Плюшкин из экономии разрезает каждый лист бумаги на три части. Некоторые из полученных листов он также режет на три части и т.д. Сколько листков бумаги он получит, если разрежет k листов?
Решение
Сделаем рисунок к условию задачи. При этом листы бумаги будем обозначать кружками: кружки, соответствующие разрезанным листам, закрасим; остальные оставим не закрашенными.
| K=1 | K=2 | K=3 |
Рисунок 1
Рисунок помогает увидеть, что при разрезании появляются три новых листика вместо одного. Таким образом, получилось 1+2*1=3 листка; если разрезали два листа, то получилось 1+2*2=5 листков; если три, то - 1+2*3=7 и т.д. Если же было разрезано k листов, то образовалось 1+2k листиков.
При решении задачи, мы получили схемы, похожие на ветку дерева с листьями..
Рисунки этой задачи оставить на доске.
Задача 1.2.
В соревнованиях по шашкам участвует шесть человек: Кирилл, Денис, Ольга, Сергей, Полина и Андрей. Соревнование проводится по круговой системе – каждый из участников играет с каждым из остальных один раз. К настоящему моменту некоторые игры уже проведены: Кирилл сыграл с Денисом, Сергеем и Андреем; Денис, как уже говорилось, с Кириллом и еще с Сергеем; Ольга – с Сергеем, Полиной, Андреем; Сергей – с Кириллом, Денисом и Ольгой; Полина – с Ольгой, а Андрей – с Кириллом и Ольгой. Сколько игр проведено к настоящему моменту и сколько еще осталось?
Решение.
Представим данные задачи на чертеже. Обозначим участников соревнования точками так, что Кириллу будет соответствовать точка К, Денису – точка Д и т.д. Если двое участников уже сыграли между собой, то соединим изображающие их точки отрезками.
Получили некоторую схему, из которой видно, что число игр, проведенных к настоящему моменту, равно Рисунок 2. количеству изображенных на ней отрезков, то есть семь.
Рисунок 3. Рисунок также остается на доске.
Чтобы найти число игр, которые осталось провести, соединим пунктирной линией еще не игравших друг с другом участников.
Таких “пунктирных” отрезков получилось восемь, то есть нужно провести еще восемь игр. Кирилл должен сыграть с Ольгой и Полиной, Денис – с Ольгой, Полиной и Андреем и т.д.
Есть ли что-нибудь общее у полученных схем? Да. Они все состоят из точек (кружков) и линий (прямых или кривых), соединяющих пары точек. Эти схемы являются представителями так называемых графов.
Определение 1.1. Графом называется совокупность двух множеств: непустого множества точек (вершин) и множества линий, соединяющих эти точки (ребер).
Обозначать граф будем буквой Г. Вершины графа будем обозначать прописными буквами русского (латинского) алфавита или числами (например, А, Б, В,…,A, B, C, D,…,1, 2,…); ребра – парами вершин, принадлежащих данным ребрам или строчными буквами русского (латинского) алфавита (например, (А,Б), (N,F), (3,4), а, б, в, k, l, m). Иногда будем изображать граф, не обозначая его ребра и вершины.
В некоторых случаях каждому ребру графа присваивают некоторое число. Это число называется весом данного ребра.
Рисунок 4.
Пример 1.1 Граф с вершинами A, B, C, D, E, ребрами (A, B), (B, D), (C, E), (E, D).
20 – вес ребра (А, В),
15 – вес ребра (С, Е) и т.д.
Вершины графа обычно изображают “жирными” точками, кружками или квадратиками, так как ребра графа иногда пересекаются на чертеже, но точка пересечения при этом не является вершиной.
Пример 1.2.
В данном графе точка пересечения диагоналей четырехугольника не является вершиной графа.
А в этом графе точка пересечения диагоналей четырехугольника является Рисунок 5. вершиной графа.
Не всегда все вершины графа соединены друг с другом. Иногда вершина не соединена ни с одной из вершин графа.
Определение 1.2. Вершина графа, не принадлежащая ни одному ребру, называется изолированной.
Рисунок 6
Пример 1.3.
Вершина 5 является изолированной.
Задание 1.1. (Устно) Рисунок 6.
Рисунок 7
Вершины графа представляют жителей городка N, а ребра, соединяющие две вершины, - тот факт, что эти люди знакомы. Какую ситуацию изображает приведенный на рисунке граф? Рисунок 7.
Решение.
Все вершины графа являются изолированными, то есть ни одна пара вершин не соединена ребром. Таким образом, все пять жителей не знакомы друг с другом.
Определение 1.3. Вершина А графа Г, принадлежащая одному ребру, называется висячей.
Пример 1.4. Вершины А и Б - висячие.
Рисунок 8.
Рисунок 9.
Задание 1.2.
Укажите висячие вершины. Объясните ответ.
Есть ли здесь изолированные вершины? Объясните ответ.
Ответ: 1, 4, 5 – висячие вершины по определению. Изолированных вершин нет по определению.
Задание 1.3. Начертите граф, содержащий 4 висячих и две изолированные вершины.
Задание 1.4. Начертите граф, содержащий шесть висячих и две изолированные вершины.
Определение 1.4. Степенью вершины А графа Г называется количество ребер графа Г, которым данная вершина принадлежит.
Обозначают степень вершины А: d(A).
В случае изолированной вершины d(A)=0; для висячей вершины d(A)=1.
Пример 1.5.
М и N – изолированные вершины.
Рисунок 10.
Задание 1.5. В следующих графах найдите степени каждой из вершин.
Рисунок 11.
Ответ:
а) d(1)=d(2)=d(3)=d(4)=d(5)=2;
б) d(1)=d(2)=d(4)=1 – это висячие вершины,
d(5)=0 – это изолированная вершина,
d(3)=2, d(6)=3.
Установим связь между степенями вершин графа и числом его ребер.
Задание 1.6. Найдите количество ребер Р графа Г и сумму степеней С всех его вершин.
А) Ответ: Р=4, С=1+2+3+2=8.
Рисунок 12.
Б) Ответ: Р=5, С=2+3+2+3=10.
Рисунок 13.
В) Ответ: Р=1, С=1+1+0=2.
Рисунок 14.
Г) Ответ: Р=7, С=4+3+2+2+3=14.
Рисунок 15.
Заметим, что в каждом случае сумма всех степеней вершин графа в два раза больше, чем число его ребер.
Теорема 1.1. Сумма степеней вершин графа Г
равна удвоенному числу ребер, то есть 
, где r – число
ребер.
Определение 1.5. Пусть дан граф Г с вершинами 
, 
, …, 
. Путем в графе Г называется
последовательность ребер 
, 
, …, 
.
Причем вершина называется началом пути, а вершина 
– концом пути.
Из определения следует, что каждые два соседних ребра пути имеют общую вершину и никакое ребро не встречается более одного раза.
Пример 1.6.
(M, B), (B, D), (D, E), (E, C), (C, N) – путь в данном графе из вершины М в вершину N.
M – начало пути; N – конец пути.
Рисунок 16.
Задание 1.7. (Устно.)
Являются ли путями из вершины 1 в вершину 5 следующие последовательности ребер:
А) (1,2),(3,4),(4,5) – нет, т.к. ребра (1,2) и (3,4) – соседние, но не имеют общей вершины;
Рисунок 17.
Б) (1,2),(2,3),(3,4) – нет, т.к. эта последовательность не ведет в вершину 5;
В) (1,2),(2,4),(4,3),(3,2),(2,4),(4,5) – нет, т.к. ребро (2,4) повторяется.
Найдите путь от вершины 1 к вершине 5 в графе, изображенном на рисунке.
Ответ: (1,2),(2,3),(3,4),(4,5) или (1,2),(2,4),(4,5).
Сравним два полученных в задаче пути. Очевидно, второй из них короче. Значит можно говорить о длине пути в графе.
Определение 1.6. Длиной пути в графе Г называется количество входящих в этот путь ребер.
Пример 1.7.
(M, B), (B, D), (D, E), (E, C), (C, N) – путь в данном графе из вершины М в вершину N.
Длина пути равна пяти.
Рисунок 18.
Задание 1.8. (Устно.)
Укажите все пути, соединяющие вершины 1 и 4 в графе, изображенном на рисунке. Сколько существует путей длины два в этом графе?
Рисунок 19.
Ответ: (1,4) и (1,2),(2,3),(3,4). Существует восемь путей длины два.
Определение 1.7. Циклом графа Г называется такой путь в этом графе, у которого начало совпадает с концом.
Пример 1.8.
(M, B), (B, D), (D, E), (E, C), (C, N), (N, M) – цикл в данном графе.
(A, B), (B, D), (D, A) – цикл в данном графе.
Рисунок 20.
Задание 1.9.
Является ли циклом следующая последовательность ребер:
Рисунок 21.
А) (A,B),(B,E),(E,D),(D,B),(B,A);
Б) (D,E),(E,B),(B,D),(D,C);
В) (D,C),(C,B),(B,E),(E,D);
Г) (B,E),(D,C),(C,B)?
Ответ:
А) нет, т.к. ребро (А,В) повторяется дважды, а значит последовательность – не путь.
Б) нет, т.к. начальная и конечная вершины не совпадают.
В) да, т.к. все условия определения цикла выполнены.
Г) нет, т.к. соседние ребра (B,E) и (D,C) не имеют общей вершины
(пропущено ребро (E,D)), а значит последовательность – не путь.
Определение 1.8. Длиной цикла называется количество входящих в него ребер.
Задание 1.10.
Для каждого из изображенных на рисунке графов назвать все содержащиеся в них циклы и выбрать наибольший и наименьший по длине цикл.
Рисунок 22.
Ответ:
а) (1,2),(2,3),(3,4),(4,5),(5,6),(6,7),(7,1) – самый длинный цикл; (1,2),(2,6),(6,7),(7,1); (2,3),(3,4),(4,6),(6,2); (1,2),(2,3),(3,4),(4,6),(6,7),(7,1); (2,3),(3,4),(4,5),(5,6),(6,2); (4,5),(5,6),(6,4) – самый короткий цикл;
б) (2,3),(3,5),(5,4),(4,2) – единственный цикл в этом графе;
в) (2,3),(3,5),(5,2) и (2,4),(4,5),(5,2) – самые короткие циклы;
(2,3),(3,5),(5,4),(4,2) – самый длинный цикл.
Посмотрите на рисунки б) и в) предыдущей задачи. Можно ли найти путь из вершины 1 в вершину 2 на рисунке б)? Да. А на рисунке в)? Нет.
Определение 1.9. Граф называется связным, если между любыми двумя его вершинами существует путь. В противном случае граф называется несвязным.
Пример 1.9.
а) 
б) в) 
Рисунок 23.
Две вершины А и В графа называются связными, если в графе существует путь с концами А и В; если не существует ни одного пути, связывающего их, то вершины называются несвязными.
Из определения следует, что граф является связным, если каждые две его вершины связны, и граф является несвязным, если хотя бы две его вершины несвязны.
Таким образом, чтобы доказать, что граф связный, нужно доказать, что каждые две его вершины являются связными. А чтобы доказать, что граф несвязный – нужно указать в нем две несвязные вершины.
Задание 1.11.
Какие из графов являются связными? Почему?
Рисунок 24.
Ответ: связными являются графы г) и д).
Определение 1.10. Ребро (А, В) называется мостом графа Г, если в графе, полученном после удаления из Г ребра (А, В), вершины А и В оказываются несвязными.
Пример 1.10.
Рисунок 25.
Задание 1.17.
Выделите в графе, изображенном на рисунке, ребра, которые являются мостами.
Рисунок 26.
Ответ: 
Рисунок 27.
Теорема 1.2. Ребро (А, В) является мостом в том и только том случае, если (А, В) – единственный путь, соединяющий вершины А и В.
Рисунок 28.
Теорема 1.3. Ребро (А, В) является мостом в том и только том случае, если найдутся две вершины С, D такие, что каждый путь, соединяющий их, содержит вершины А и В.
Рисунок 29.
Теорема 1.4. Ребро (А, В) является мостом в том и только том случае, если оно не принадлежит ни одному циклу.
Литература.
- Башмаков М. И. Алгебра и начала анализа: Учебник для 10-11 кл. средн. школы. – М.: Просвещение, 1993.
- Белов В. В., Воробьев Е. М., Шаталов В. Е. Теория графов. – М.: Высшая школа, 1976.
- Березина Л. Ю. Графы и их применение: пособие для учителей. – М.: Просвещение, 1979.
- Берж К. Теория графов и ее применения/Пер.с франц. Зыкова А. А., под ред. Вайнштейна И. А. – М.: Изд-во иностр. литер., 1992.