Теория графов

Графы - это замечательные математические объекты, с помощью, которых можно решать математические, экономические и логические задачи. Также можно решать различные головоломки и упрощать условия задач по физике, химии, электронике, автоматике. Графы используют при составлении карт и генеалогических древ. Графами являются блок-схемы программ для ЭВМ, сетевые графики строительства, где вершины – события, означающие окончания работ на некотором участке, а ребра, связывающие эти вершины, - работы, которые возможно начать по совершении одного события и необходимо выполнить для совершения следующего. Одними из самых распространённых графов являются схемы линий метрополитена.

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

1. Понятие графа

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

В математике определение графа дается так:

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

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

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

Первая работа по теории графов принадлежит Леонарду Эйлеру (1736 год), хотя термин «граф» впервые ввел в 1936 году венгерский математик Денеш Кениг.

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

Схема графа, состоящая из «изолированных» вершин, называется нулевым графом.

Графы, в которых не построены все возможные ребра, называются неполными графами.

Графы, в которых построены все возможные ребра, называются полными графами.

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

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

2. Степени вершин и подсчет числа ребер.

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

Если степени всех вершин графа равны, то граф называется однородным. Таким образом, любой полный граф — однородный.

Сформулируем некоторые закономерности, присущие определенным графам.

Закономерность 1.

Степени вершин полного графа одинаковы, и каждая из них на 1 меньше числа вершин этого графа.

Доказательство:

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

Закономерность 2.

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

Эта закономерность справедлива не только для полного, но и для любого графа.

Доказательство:

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

ТЕОРЕМА.

Число нечетных вершин любого графа четно.

Доказательство:

Рассмотрим произвольный граф Г. Пусть в этом графе число вершин, степень которых 1, равна К1; число вершин, степень которых 2, равно K2;. ; число вершин, степень которых n, равно Кn. Тогда сумму степеней вершин этого графа можно записать как

K1 + 2К2 + ЗК3 +. + nКn.

С другой стороны: если число ребер графа R, то из закономерности 2 известно, что сумма степеней всех вершин графа равна 2R. Тогда можно записать равенство

K1 + 2К2 + ЗК3 +. + nКn = 2R. (1)

Выделим в левой части равенства сумму, равную числу нечетных вершин графа (К1 + К3 +. ):

K1 + 2К2 + ЗК3 + 4К4 + 5К5 +. + nК = 2R,

(К1 + К3 + К5 +. ) + (2K2 + 2Х3 +4K4 + 4К5 +. )=2R

Вторая скобка- четное число как сумма четных чисел. Полученная сумма (2R) четное число. Отсюда (К1 + К3 + К5 +. )-четное число.

Заметим, что если полный граф имеет n вершин, то количество ребер будет равно n(n-1)/2

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

Граф, не являющийся полным, можно дополнить до полного с теми же вершинами, добавив недостающие ребра. Так, например, на рисунке 3 изображен неполный граф с пятью вершинами. На рисунке 4 ребра превращающие граф в полный граф изображены другим цветом, совокупность вершин графа с этими ребрами называется дополнением графа.

3. Эйлеровы графы.

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

Такими графы названы в честь учёного Леонарда Эйлера.

Закономерность 3 (вытекает из рассмотренной нами теоремы).

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

Закономерность 4.

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

Закономерность 5.

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

Закономерность 6.

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

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

4. Связные графы.

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

Граф называется несвязным, если это условие не выполняется.

Такое ребро в теории графов (после удаления которого граф из связного превращается в несвязный) называется мостом.

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

ТЕОРЕМА.

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

Доказательство:

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

5. Деревья.

Деревом называется любой связный граф, не имеющий циклов.

Договорились считать «деревом» и всякий граф, состоящий из одной (изолированной) вершины.

Циклом называется путь, в котором совпадают начало с концом.

Если все вершины цикла разные, то такой цикл называется элементарным (или простым) циклом. Если же цикл включает в себя все ребра графа по одному разу, то такой цикл называется Эйлеровой линией (рис. 9а). В графе на рис. 9б два цикла: 1-2-3-4-1 и 5-6-7-5.

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

При этом никакое ребро маршрута не должно встречаться более одного раза. Вершина, от которой проложен маршрут, называется началом пути, вершина в конце маршрута — конец пути.

Висячей вершиной называется вершина, из которой выходит ровно одно ребро.

рис. 10 (кружком обведены висячие вершины)

Свойство 1.

Для каждой пары вершин дерева существует единственный путь, их соединяющий.

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

Свойство 2.

Всякое ребро в дереве является мостом.

Действительно, после удаления любого ребра дерева, оно «распадается» на два дерева.

Граф, в котором две любые вершины соединены ровно одним простым путём, является деревом.

Доказательство:

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

*Дерево – это граф, в котором две любые вершины соединены ровно одним простым путём.

ЛЕММА (о висячей вершине)

В каждом дереве есть висячая вершина.

Доказательство:

Рассмотрим произвольную вершину дерева и пойдём по любому выходящему из неё ребру в другую вершину. Если из новой вершины больше рёбер не выходит, то мы остаёмся в ней, а противном случае, идём по любому другому ребру дальше. Понятно, что в этом путешествии мы никогда не сможем попасть в вершину, в которой уже побывали: это означало бы наличие цикла. Так как у графа конечное число вершин, то наше путешествие обязательно должно закончится. Но закончиться оно может только в висячей вершине. Лемма доказана.

ТЕОРЕМА.

В дереве число вершин на одну больше числа ребер.

Доказательство:

Из условия теоремы граф – дерево. У него есть висячая вершина. Удалим её и выходящее из нее ребро. Оставшийся граф также дерево. У него есть висячая вершина, которую также удалим. Проделав эту операцию n-1 раз, получим граф, состоящий из одной вершины. Т. к. удалялось по одному ребру, то вначале их было n-1.

6. Изоморфизм. Плоские графы и теорема Эйлера.

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

Докажем, что графы изображенные на рисунке 11 изоморфны.

Пронумеруем вершины первого и второго графов от 1и до 4.

В первом графе соединены вершины 1 и 2, 2 и 3, 3 и 4, 1 и 4, 1 и 3, 2 и 4; заметим, что во втором графе также соединены вершины 1 и 2, 2 и 3, 3 и 4, 1 и 4, 1 и 3, 2 и 4, следовательно, данные графы изоморфны.

Для того, чтобы выяснить, изоморфны ли два графа, нужно убедиться в том, что у них:

одинаковое количество вершин если вершины одного графа соединены ребром, то и соответствующие им вершины другого графа тоже соединены ребром.

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

ТЕОРЕМА Эйлера.

Для правильно нарисованного связного плоского графа имеет равенство: V-E+F=2, где V – число вершин, E - число рёбер, F – число кусков.

(равенство V-E+F=2 обычно называют формулой Эйлера)

Доказательство:

Будем удалять рёбра графа до тех пор, пока не получим дерево. Посмотрим, как при удалении очередного ребра изменяются величины V, E и F. Ясно, что число вершин не изменяется, а количество рёбер уменьшается на один. Число кусков также уменьшается на один, так как при удалении ребра два примыкающих к нему куска сливаются в один. Поэтому V-E+F при такой операции не изменяется. Так как для полученного дерева V-E=1 и F=1, то V-E+F=2 и, следовательно, для исходного графа также выполняется это равенство. Значит, теорема доказана.

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

ТЕОРЕМА Понтрягина – Куратовского:

Граф является плоским тогда и только тогда, когда он не содержит (в топологическом смысле) графа с шестью вершинами типа «домики-колодцы» и полного графа с пятью вершинами. (В основном используется старинных задач о домах и колодцах, суть которой сводится к выяснению вопроса — является ли рассматриваемый граф плоским или нет)

7. Ориентированные графы.

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

Так, например, схема дорог и площадей города изображается с помощью плоского графа. Но если нужно этой схемой воспользоваться с целью проезда по городу на автомашине, а движение на отдельных (или на всех) улицах одностороннее?

Тогда могут помочь сориентироваться в этой ситуации стрелки, расположенные, например, прямо на ребрах-улицах рассматриваемой схемы (графа) города.

Граф, на рёбрах которого расставлены стрелки, называется ориентированным.

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

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

Так, на рисунке 15 изображен ориентированный граф АБВГД. Степени входа и выхода некоторых его вершин такие:

Ст. вх. А=2, Ст. вых. А=1

Ст. вх. В=2, Ст. вых. В=0

Ст. вх. Д=1, Ст. вых. Д=3

Путем, в ориентированном графе от вершины А1 к вершине An называется последовательность ориентированных ребер

A1A2, A2A3,. , Аn-1Аn в которой конец каждого предыдущего ребра совпадает с началом следующего и каждое ребро встречается в этой последовательности только один раз.

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

Ориентированным циклом называется замкнутый путь в ориентированном графе.

На предыдущем рисунке приведены примеры ориентированных циклов в последних двух графах. Цикл, как и любой другой путь в графе, имеет длину, которая определяется числом ребер в этом пути.

Так пути от А к Д могут быть различны и иметь различную длину.

Первый путь имеет длину 2, второй - 3, а третий — 4.

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

Так расстояние между вершинами А и Д на графе рисунка 16 равно 2; записывают так: S(АД)=2.

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

Так, расстояние между вершинами Б и Д графа, представленного на рисунке 17 бесконечно: S(БД) = ∞

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

8. ЗАДАЧИ.

Между планетами введено космическое сообщение по следующим маршрутам: З-К, П-В, З-П, П-К, К-В, У-М, М-С, С-Ю, Ю-М, М-У. Можно ли добраться с З до М?

Решение:

Составим схему-граф маршрутов:

Мы видим, что от З до М добраться нельзя.

25 борцов играют по олимпийской системе (проигравший выбывает). За какое наименьшее количество встреч можно определить победителя?

Решение:

После каждой встречи 1 боец выбывает, в конце останется только один боец, значит наименьшее количество встреч 24.

Решение:

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

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

Кенигсбергские мосты.

К XVIII веку через реку, на которой стоял город Кенигсберг (ныне Калининград), было построено 7 мостов, которые связывали с берегами и друг с другом два острова, расположенные в пределах города (см. рисунок)

Задача заключается в следующем: нужно пройти (если это возможно) по всем семи мостам так, чтобы на каждом из них побывать лишь по одному разу и вернуться к тому месту, откуда начал маршрут.

Решение:

Решить эту задачу удалось в 1736 г. Леонарду Эйлеру. В ходе решения задачи (после интерпретации условия задачи в виде графа, где вершины - острова и берега, а ребра - мосты, представленного на рисунке. )

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

В трех различных домах живут три поссорившиеся между собой соседа. Недалеко от их домов имеются три колодца. Можно ли от каждого дома проложить к каждому из колодцев тропинку так, чтобы никакие две из них не пересекались?

Решение:

Построим граф, вершины которого

А, Б, В, 1, 2, 3 соответствуют домам и колодцам условия задачи, и попробуем доказать, что девятую тропинку — ребро графа, не пересекающее остальные ребра, провести нельзя.

Проведенные в графе на рисунке ребра А1, А2, A3 и В1,В2, ВЗ (соответствующие тропинкам от домов А и В ко всем колодцам). Построенный граф разбил плоскость на три области: X, У, Z. Вершина Б, в зависимости от ее расположения на плоскости, попадает в одну из этих трех областей. Если вы рассмотрите каждый из трех случаев «попадания» вершины Б в одну из областей X, Y или Z, то убедитесь, что всякий раз одна из вершин графа 1, 2 или 3 (один из колодцев) будет «недоступной» для вершины Б (т. е. нельзя будет провести одно из ребер Б1, Б2 или Б3. которое не пересекло бы уже имеющихся в графе ребер).

Таким образом, ответ на вопрос задачи будет таким: «Нельзя!»

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

В городе Н от каждой площади отходит ровно 5 улиц, соединяющих площади. Докажите, что число площадей чётно, а число улиц кратно 5.

Решение:

По теореме, что число нечётных вершин любого графа чётно, следует, что число площадей (вершин графа) 2n, а число улиц (рёбер графа) будет (2n·5):2, а значит, число площадей чётно, а число улиц кратно 5.

Футбольный мяч сшит из 32 лоскутов: белых шестиугольников и чёрных пятиугольников. Каждый чёрный лоскут граничит только с белыми, а каждый белый – с тремя чёрными и тремя белыми. Сколько лоскутов белого цвета?

Решение:

Пусть на мяче число белых лоскутов х шт. , а чёрных будет (32 – х) шт. Тогда границ белых лоскутов с чёрными 5(32-х)=3х, значит, х=20 и белых лоскутов 20 шт.

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

Решение:

Пусть существует некоторый город А. Из него можно добраться не более, чем до трёх городов, а из каждого из них ещё не более чем до двух (не считая А). Тогда всего городов не более 1+3+6=10. Значит всего городов не более 10. Пример на рисунке (его ещё называют графом Петерсона) показывает существование авиалиний.

Можно ли нарисовать графы изображенные на рисунках, не отрывая карандаш от бумаги и проводя каждое ребро ровно один раз?

Решение:

1) Можно, т. к. только 2 нечетные вершины.

2) Нельзя, т. к. 4 нечетные вершины.

Все города страны, кроме столицы, расположены вдоль шоссе. Из столицы в каждый город ведет прямая дорога. Две компании хотят приватизировать дороги и участки шоссе так, чтобы каждая компания могла проехать из любого города в любой другой только по своим дорогам. Смогут ли они это сделать при каком-нибудь числе городов, большем одного?

Решение:

Допустим, что это возможно, тогда пусть на шоссе n городов, значит дорог всего (2n-1). Поскольку дороги одной компании соединяют все города в связное множество, то этих дорог не меньше n. Тогда дорог двух компаний не меньше 2n, что нам противоречит, а значит, не смогут выполнить условия.

Нарисовать плоский граф, имеющий 6 вершин, степень каждой из которых равна а)3 б)4.

Решение:

Дима, приехав из Врунляндии, рассказал, что там есть несколько озёр, соединенных между собой реками. Из каждого озера вытекают 3 реки, и в каждое озеро впадают 4 реки. Докажите, что он ошибается.

Решение:

Если вытекают 3 реки, а впадают 4 – это невозможно, т. к. количество «втекающих», должно быть равно количеству «вытекающих». Дима не прав.

Какие-то две команды набрали в круговом волейбольном турнире одинаковое число очков. Докажите, что найдутся команды А, В и С такие, что А выиграла у В, В выиграла у С, а С выиграла у А.

Решение:

Пусть А и В набрали одинаковое количество очков, но В выиграла у А, тогда если для любой команды С, у которой выиграла А, выиграла и В, то у В должно быть очков больше, чем у А. Значит, есть такая команда С, что А выиграла у С, а С выиграла у В.

В Цветочном городе каждый коротышка знаком с 6 малышками, а каждая малышка – с 6 коротышками. Докажите, что в этом городе число малышек равно числу коротышек.

Решение:

Если знакомство вида «коротышка – малышка» - это ребро графа, то n – число коротышек, m – число малышек. Тогда всех знакомств (ребер) коротышек 6n, а малышек 6m. Значит 6n= 6m, тогда в этом городе число малышек равно числу коротышек.

Мы знаем, что у изоморфных графов некоторых ребра пересекаются. А всегда ли граф можно изобразить на плоскости так, чтобы его рёбра не пересекались? Оказывается, нет. Графы, для которых это возможно называются плоскими.

В трёх избушках жили трое друзей. Около их домиков находилось три колодца: один с солёной водой, второй – со сладкой, а третий – с пресной. Но однажды друзья поссорились, да так, что и видеть друг друга не хотели. И решили они по-новому проложить тропинки от домов к колодцам, чтобы их пути не пересекались. Как это сделать? На рисунке проведено восемь из девяти тропинок, но провести девятую уже не удаётся.

Второй граф, с шестью вершинами и девятью рёбрами, носит название «домики - колодцы». Оно произошло от старинной задачи-головоломки.

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

Плоские графы обладают многими интересными свойствами. Так, Эйлер обнаружил простую связь между количеством вершин (B), количеством рёбер (Р) и количеством кусков (К) на которые разделяется плоскость:

В – P + К = 2

Если вспомнить, как с помощью лампочки плоский граф, изоморфный графу, состоящему из вершин и рёбер выпуклого многогранника, то легко понять, что эта формула верна для любого выпуклого многогранника. Этот факт, как недавно выяснилось, был известен ещё Рене Декарту.

Барон Мюнхаузен, прилетев с Луны, рассказал, что в каждое лунное море впадает пять рек, а из каждого лунного моря вытекает шесть рек. Докажите, что он говорит неправду

Решение:

Пусть на Луне N морей. Посчитаем реки двумя способами: по тому, откуда они вытекают, и по тому, куда они впадают. Первым способом получается, что рек 6N, а вторым - что 5N. Противоречие, ч. т. д.

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

В королевстве каждый город соединен с каждым дорогой. Может ли сумасшедший король вместе на дорогах одностороннее движение так, чтобы, выехав из любого города, в него нельзя было вернуться?

Решение:

Тут мы имеем дело с другим видом задач: введением ориентации (с заданными свойствами) на обычном графе. Попробуем придумать простенькие примеры (см. рисуное).

Интересно. в каждом примере все ребра идут именно слева направо (особенно легко это получается, если каждый следующий пример строить как расширение предыдущего!). Так давайте всегда проводить все ребра слева направо (при этом избегая рисовать вершины в точности друг над другом). Тогда, выехав из любого города, мы будем оказываться все правее и правее, и никогда не вернемся в исходную точку. Значит, можно.

Можно формализовать это и без геометрических соображений о том, как нарисован граф: занумеровать все вершины и ставить все стрелки от меньшего номера к большему.

Замечание.

В построенном графе каждая вершина - отдельная компонента сильной связности.

Дан кусок проволоки, длиной 120 см. Можно ли, не ломая проволоки, изготовить каркас куба с ребром 10 см?

Решение:

Если куб – граф, тогда он имеет более двух нечетных вершин (8). Значит, невозможно изготовить такой каркас, не ломая проволоки.

Можно ли обвести карандашом, не отрывая его от бумаги и не проходя по одной линии дважды, правильный пятиугольник с диагоналями?

Решение:

Если пятиугольник – граф и все вершины его четные – то это выполнить можно.

Длина окружности переднего колеса кареты равна 3 м, а заднего 4,5 м. Какое расстояние проехала карета, если переднее колесо сделало на 20 оборотов больше заднего?

Решение:

Обозначим расстояние, которое проехала карета L, длину окружности колеса – с, число сделанных оборотов- n. Очевидно, что эти величины связаны соотношением L = c * n, поэтому мы будем решать задачу с помощью сетевых графов.

L-nn-n3, х/3>х/4,5, на 20, значит, х/3-х/4,5=20.

Пусть от одной станции до другой товарный поезд прошёл за 9 ч, а пассажирский за 6 ч. Найдите скорость пассажирского поезда, если скорость товарного поезда равна 40 км/ч.

Решение:

В этой задаче один и тот же путь проходит с разными скоростями, поэтому кружок S- общий; можно использовать обозначения Sт и Sп, Vт и Vп, tт tп,а не S1,V1,t1,S2,V2,t2.

ЗАКЛЮЧЕНИЕ:

Выделяя из словесных рассуждений главное - объекты и отношения между ними, графы представляют изучаемые факты в наглядной форме. Приёмы решения логических задач с использованием графов подкупают своей естественностью и простотой, избавляют от лишних рассуждений, во многих случаях сокращающих нагрузку на память. С одной стороны, графы помогают проследить все логические возможности изучаемой ситуации, с другой, благодаря своей обозримости, помогают тут же, в ходе решения задачи, классифицировать логические возможности, отбрасывать неподходящие случаи, не доводя до полного перебора всех случаев. Что подтверждает нашу гипотезу.

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

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

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