Графы. Теоретическое знакомство (первые начинания)
Муниципальное бюджетное образовательное учреждение
Октябрьская средняя общеобразовательная школа
Исследовательская работа по математике
«Теория графов при решении различных
видов задач»
Выполнил:
ученик 7 б класса
Макшун Алексей
Руководитель:
учитель математики
Мошково 2011 год
|
Введение. | ||
|
Актуальность выбранной темы. | ||
|
История возникновения теории графов. | ||
|
Основная часть. | ||
|
Основные понятия теории графов. Применение ее при решении логических задач. | ||
|
Эйлеровы пути. Построение фигуры одним росчерком. | ||
|
Плоские графы. | ||
|
Заключение. | ||
|
Литература. |
1. Введение.
1. 1. Актуальность выбранной темы.
Однажды мне встретилась задача, описанная Льюсом Кэрроллом. «Три человека жили в трех домиках, неподалеку от них находились три колодца: один с водой, другой с маслом, а третий с повидлом, и ходили к ним по тропинкам, изображенным на рисунке. Однажды эти люди перессорились и решили провести тропинки от своих домов к колодцам так, чтобы эти тропинки не пересекались».
Я пытался решить эту задачу, но у меня нечего не получалось. После этого я обратился к своему учителю, и мне объяснили, что решить эту задачу я могу, только изучив теорию графов. Но прежде, чем найти ответ на свой вопрос, я увидел, что теория графов помогает упростить решение многих задач. Графы заинтересовали меня своей возможностью помогать в решении различных головоломок, математических и логических задач.
Цель:
Показать применение теории графов для решения различных видов задач.
Задачи:
· Изучить элементы теории графов для решения интересующих меня задач.
· Разобрать решение различных видов задач.
· Повысить математическую культуру.
1.2. История возникновения теории графов.
Датой рождения теории графов принято считать 1736 год, когда Леонард Эйлер решил задачу о кенигсбергских мостах. Рукава реки Прегель, на берегу которой расположен город Кенигсберг, образовывали два острова. В эту эпоху четыре образовавшихся участка суши (правый и левый берег и два острова) соединяло семь мостов так, как это показано на рисунке. Горожане, гуляя по городу, пытались составить маршрут, чтобы он проходил по каждому мосту ровно один раз. Это им не удавалось, а Эйлер доказал, что это принципиально невозможно. Термин «граф» впервые ввел в 1936 году венгерский математик Денеш Кениг. Широкое развитие теория графов получила с 50-х годах 20 века в связи со становлением кибернетики и развитием вычислительной техники.
Слово «граф» в математике означает картинку, где нарисовано несколько точек, некоторые из которых соединены линиями. С дворянским титулом «граф» их связывает общее происхождение от латинского слова «графио» - пишу.
Примерами графов могут служить схемы авиалиний , метро, дорог, электросхемы, чертежи многоугольников.
Схема Новосибирского метрополитена.
Использует графы и дворянство. Например, в генеалогическом дереве, вершины – члены рода, а связывающие их отрезки – отношения родственности.
Генеалогическое дерево.
С помощью графов часто упрощается решение задач, сформулированных в различных областях знаний: в автоматике, электронике, физике, химии. Помогают графы в решении математических и экономических задач .
2. Основная часть.
2.1. Основные понятия теории графов. Применение ее при решении логических задач.
В математике определение графа дается так:
Графом называется конечное множество точек, некоторые из которых соединены линиями. Точки называются вершинами графа, а соединяющие линии – рёбрами.
Схема графа, состоящая из «изолированных» вершин, называется нулевым графом. (рис.2)
Графы, в которых не построены все возможные ребра, называются неполными графами. (рис.3)
Графы, в которых построены все возможные ребра, называются полными графами. (рис.4)
Количество рёбер, выходящих из вершины графа, называется степенью вершины . Вершина графа, имеющая нечётную степень, называется нечетной , а чётную степень – чётной .
Если степени всех вершин графа равны, то граф называется однородным . Таким образом, любой полный граф - однородный.
На рисунке 5 изображен граф с пятью вершинами. Степень вершины А обозначим Ст. А. На рисунке: Ст. А = 1, Ст. Б = 2, Ст. В = 3, Ст. Г= 2, Ст. Д= 0.
Задача №1.
Аркадий, Борис. Владимир, Григорий и Дмитрий при встрече обменялись рукопожатиями (каждый пожал руку каждому по одному разу). Сколько всего рукопожатий было сделано?
Решение:
Пусть каждому из пяти молодых людей соответствует определенная точка на плоскости, названная первой буквой его имени, а производимому рукопожатию - отрезок или часть кривой, соединяющая конкретные точки - имена.
Задача №2.
В одном дворе живут четыре друга. Вадим и шофер старше Сергея, Николай и слесарь занимаются боксом, электрик-младший из друзей.
По вечерам Андрей и токарь играют в домино против Сергея и электрика.
Определите профессию каждого из друзей.
Решение.
Составим граф из 4 друзей и 4 профессий. Пунктирными линиями отметим невозможные связи, а сплошной - соответствие имени и профессии. Если от каждой вершины выходить 3 пунктирных линии, то четвертая линия должна быть сплошной.
В С Н А
 |
Ш С Т Э
Задача №3.
В небольшом городке живут пять друзей: Иванов, Петренко, Сидорчук, Гришин и Капустин. Профессии у них разные: один из них маляр, другой - мельник, третий- плотник, четвертый-почтальон, а пятый - парикмахер.
Петренко и Гришин никогда не держали в руках малярной кисти.
Иванов и Гришин собираются посетить мельницу, на которой работает их товарищ. Петренко и Капустин живут в одном доме с почтальоном.
Сидорчук был недавно в ЗАГСе одним из свидетелей, когда Петренко и дочь парикмахера сочетались законным браком. Иванов и Петренко каждое воскресенье играют в городки с плотником и маляром.
Гришин и Капустин по субботам обязательно встречаются в парикмахерской, где работает их друг. Почтальон предпочитает бриться сам. Кто есть кто?
Решение.
Иванов Петренко Сидорчук Гришин Капустин
 |
маляр мельник плотник почтальон парикмахер
2.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 + К3 + ...):
K1 + 2К2 + ЗК3 + 4К4 + 5К5 + ... + nКn = 2R,
(К1 + К3 + К5 +...) + (2K2 + 2K3 +4K4 + 4К5 + ...)=2R
Вторая скобка - четное число как сумма четных чисел. Полученная сумма (2R) четное число. Отсюда (К1 + К3 + К5 +...)-четное число.
Что и требовалось доказать.
Задача №4.
Можно ли 25 приборов соединить проводами так, чтобы каждый прибор был соединен ровно с пятью другими?
Решение.
Невозможно. В таком графе было бы нечетное число вершин нечетной степени.
Заметим, что если полный граф имеет n
вершин, то количество ребер будет равно n(n-1)/2. Действительно, количество ребер в полном графе с n
вершинами определяется как число неупорядоченных пар, составленных из всех n
точек-ребер графа, т. е. как число сочетаний из n
элементов по 2:
Граф, не являющийся полным, можно дополнить до полного с теми же вершинами, добавив недостающие ребра. Так, например, на рисунке 3 изображен неполный граф с пятью вершинами. На рисунке 4 ребра превращающие граф в полный граф изображены другим цветом, совокупность вершин графа с этими ребрами называется дополнением графа.
Задача №5.
В первенстве класса по настольному теннису 6 участников: Андрей, Борис Виктор, Галина, Дмитрий и Елена. Первенство проводят по круговой системе – каждый из участников играет с каждым из остальных один раз. К настоящему моменту некоторые игры уже проведены: Андрей сыграл с Борисом, Галиной, Еленой; Борис – с Андреем, Галиной; Виктор – с Галиной, Дмитрием, Еленой; Галина – с Андреем, Виктором и Борисом. Сколько игр проведено к настоящему моменту и сколько еще осталось?
Решение:
Построим граф. Сыгранные игры отметим синими линиями, красными дополним до полного графа. Получим, что сыграно 7 игр, а осталось – 8. Можно проверить: в графе 6 вершин тогда всего ребер 6*5/2=15 (7+8).
Эйлеровы графы.
Эйлеров путь - путь в графе, проходящий через каждое ребро ровно один раз.
Граф, который можно нарисовать, не отрывая карандаша от бумаги, называется эйлеровым. (рис.6) Такими графы названы в честь учёного Леонарда Эйлера.
рис.6 (эйлеровы графы)
Закономерность 3 (вытекает из рассмотренной нами теоремы).
Невозможно начертить граф с нечетным числом нечетных вершин.
Закономерность 4.
Если все вершины графа четные, то можно не отрывая карандаш от бумаги («одним росчерком»), проводя по каждому ребру только один раз, начертить этот граф. Движение можно начать с любой вершины и закончить его в той же вершине.
Закономерность 5.
Граф, имеющий всего две нечетные вершины, можно начертить, не отрывая карандаш от бумаги, при этом движение нужно начать с одной из этих нечетных вершин и закончить во второй из них.
Закономерность 6.
Граф, имеющий более двух нечетных вершин, невозможно начертить «одним росчерком».
Фигура (граф), которую можно начертить, не отрывая карандаш от бумаги, называется уникурсальной.
Задача № 6 о кенигсбергских мостах.
Рукава реки Прегель, на берегу которой расположен город Кенигсберг, образовывали два острова. В эту эпоху четыре образовавшихся участка суши (правый и левый берег и два острова) соединяло семь мостов так, как это показано на рисунке. Горожане, гуляя по городу, пытались составить маршрут, чтобы он проходил по каждому мосту ровно один раз.
Решение.
Эту задачу решил Леонард Эйлер. Он построил следующий граф и получил, что все четыре вершины нечетные, то есть нельзя пройти по всем мостам один раз и закончить путь там, где он был начат.
Задача № 7.
Четыре острова соединены между собой и с берегами реки 14 мостами так, как это показано на рисунке. Можно ли за одну прогулку обойти все эти мосты, побывав на каждом из них один раз?
Решение. Построим граф. Имеются две нечетные вершины В и С. Следовательно за одну прогулку можно обойти все мосты, побывав на каждом из них один раз. При этом прогулку надо начинать с острова В и заканчивать на острове С или наоборот.
Задача №8.
Можно ли нарисовать графы, изображенные на рисунках, не отрывая карандаш от бумаги и проводя каждое ребро ровно один раз?
Решение:
1) Можно, т. к. только 2 нечетные вершины.
2) Нельзя, т. к. 4 нечетные вершины.
Задача №9.
Говорят, что Магомет вместо подписи (он был неграмотен) описывал одним росчерком состоящий из двух рогов луны знак, представленный на рисунке. Возможно ли это?
Решение. Да, потому что в данном случае мы имеем дело с вершинами четного порядка.
Задача №10. Муха в банке.
Муха забралась в банку из-под сахара. Банка имеет форму куба. Сможет ли муха последовательно обойти все 12 ребер куба, не проходя дважды по одному ребру? Подпрыгивать и перелетать с места на место не разрешается.
Решение.
Ребра и вершины образуют граф, все 8 вершин которого имеют 3 степень, и, следовательно, требуемый обход невозможен.
Задача № 11.
Попробуйте построить данные фигуры одним росчерком.
2.3. Плоские графы.
Интересующая меня задача «о трёх домах и трёх колодцах» подтолкнула развитие теории графов. Граф, который можно нарисовать на плоскости так, чтобы его рёбра не пересекались нигде, кроме вершин, называются плоским или планарным.
Эйлер доказал теорему, которая даёт отрицательный ответ на вопрос этой задачи.
Теорема Эйлера.
Если граф, имеющий n вершин и m ребер,- плоский, тогда справедливо равенство n-m+p=2, где p количество непересекающихся частей (их называют гранями), на которые этот граф разбивает плоскость.
Доказательство.
Граф «три дома и три колодца» имеет шесть вершин и девять рёбер. Если он плоский, количество граней p должно быть равно p = n – m + 2 = 9 - 6 + 2 = 5. Но так как никакие два дома или два колодца не соединены между собой, каждая грань имеет, по меньшей мере, четыре ребра. Получим неравенство 2n ≥ 4p(каждое ребро считается два раза), откуда получаем ложное неравенство 18 ≥ 20. Аналогично доказывается, что полный пятивершинный граф также не может быть плоским.
Теорема Понтрягина – Куратовского.
Граф является плоским тогда и только тогда, когда он не содержит графа с шестью вершинами типа «домики-колодцы» и полного графа с пятью вершинами.
3. Заключение.
Чтобы найти ответ на интересующую меня задачу, мне пришлось познакомиться с новым разделом математики «Теорией графов», который не изучается в школьном курсе, но облегчает решение многих задач, я узнал много нового, понял, что математика интересна, но и трудна.
Графы – это замечательные математические объекты, с помощью, которых можно решать математические, логические и экономические задачи. Решение многих математических задач упрощается, если удается использовать графы. Представление данных в виде графа придает им наглядность и простоту. Многие математические доказательства также упрощаются, приобретают убедительность, если пользоваться графами. Также можно решать различные головоломки и упрощать условия задач по физике, химии, электронике, автоматике. Графы используются при составлении карт и генеалогических древ.
4. Литература.
3. Игнатьев смекалка. - М.: «Омега», 1994г.
5. "Математика" - приложение к газете "Первое сентября" №7,2005г
6. Энциклопедический словарь юного математика / Сост. А.П. Савин.- М.: Педагогика, 1989.
Так же использовались данные со следующих сайтов:
Энциклопедический словарь юного математика / Сост. А.П. Савин.- М.: Педагогика, 1989.
Башмаков в кармане «Кенгуру». - М.: Дрофа, 2010г.
Http:infometronovosibirsk_metro_map. htm
Http://www. /index. php? cnt=4
Физико-математический журнал «Квант», №6, 1994г.
Подготовка школьников к олимпиадам по математике. 5-6 классы./сост. – М. : «Глобус», 2009 г.
Макеева работа по математике. – Саратов: «Лицей», 2002 г.
"Математика"- приложение к газете "Первое сентября" №7,2005г
Физико-математический журнал «Квант», №6, 1994г.
Башмаков в кармане «Кенгуру». - М.: Дрофа, 2010г.
Физико-математический журнал «Квант», №6, 1994г.
Подготовка школьников к олимпиадам по математике. 5-6 классы./сост. – М. : «Глобус», 2009 г.
Физико-математический журнал «Квант», №6, 1994г.
Башмаков в кармане «Кенгуру». - М.: Дрофа, 2010г.
Макеева работа по математике. – Саратов: «Лицей», 2002 г.
Макеева работа по математике. – Саратов: «Лицей», 2002 г.
Игнатьев смекалка. - М.: «Омега», 1994г.
Макеева работа по математике. – Саратов: «Лицей», 2002 г.
Подготовка школьников к олимпиадам по математике. 5-6 классы./сост. – М. : «Глобус», 2009 г.
Башмаков в кармане «Кенгуру». - М.: Дрофа, 2010г.
При выводе уравнений скоростей ферментативных реакций используется ряд упрощающих допущений. В частности, как правило, принимают, что ферментативная реакция протекает в условиях идеального перемешивания, термо- и рН-статирования и что в реакции очень быстро устанавливается квазистационарное состояние (см. раздел 2.1), в котором все промежуточные формы фермента находятся в равновесии друг с другом. Приставка «квази» означает, что лишь часть переменных достигает стационарных значений, тогда как остальные продолжают медленно меняться. Использование допущения о достижении частью концентраций (биохимической системы квазистационарных значений известно в литературе как метод Боденштейна - Семенова . Этот метод позволяет резко упростить анализ (био)химических систем. Вместо решения систем нелинейных дифференциальных уравнений, описывающих изменение промежуточных веществ в ходе реакции, в соответствии с этим методом удается решать лишь системы алгебраических уравнений, связывающих друг с другом
квазистационарные концентрации промежуточных веществ. Основная причина, из-за которой в ферментативной реакции устанавливается квазистационарное состояние, заключается в том, что концентрация фермента обычно на несколько порядков меньше, чем концентрации субстратов, взаимодействующих с ферментом .
Как правило, системы алгебраических уравнений, описывающих квазистационарные состояния ферментативных реакций, линейны, так как взаимопревращения между промежуточными формами и комплексами представляются мономолекулярными реакциями. Поэтому для определения квазистационарных концентраций промежуточных веществ используются методы линейной алгебры. В последние годы для этой цели стали широко применяться методы теории графов .
Графом ферментативной реакции называется совокупность узлов, соответствующих квазистационарным концентрациям всех ферментных комплексов и соединяющих их направленных ветвей, характеризуемых некоторой величиной равной константе скорости превращения При этом называемая величиной или передачей ветви, может быть функцией концентрации вещесгва, участвующего в данном превращении. Концентрация этого вещества считается в квазистационарном состоянии постоянной.
Например, ферментативная реакция
протекающая через промежуточное образование двух фермент-субстратных комплексов
может быть представлена в квазистационарном состоянии графом, имеющим три узла и шесть направленных ветвей. На графе (1.11) указаны величины ветвей; две из них зависят от концентраций считающихся в квазистационарном состоянии постоянными.
Деревом графа, направленным в узел, называется незамкнутая совокупность ветвей, направленных от всех узлов графа к узлу. Дерево не имеет замкнутых или параллельных последовательностей. Величиной дерева называется произведение величин всех его ветвей. Например, узлы графа (1.11) имеют следующие деревья (их величины приведены):
(см. скан)
Так как в исходном графе имеется вся информация, необходимая для расчетов, при вычерчивании деревьев обычно не используют обозначения узлов и величин ветвей. Более того, при достижении некоторого навыка величины деревьев выписывают прямо по исходному графу - без вычерчивания деревьев.
Совокупности (на стр. 24) не являются деревьями узла так как а представляет собой замкнутую последовательность ветвей (цикл), имеет две параллельные последовательности ветвей соединяющих узлы и в имеет цикл ветвь направлена от узла в узел не связан с узлом
Базовым определителем узла называется сумма величин всех деревьев, направленных в узел - базу. Определителем графа называется сумма всех базовых определителей графа. Например, определителями узлов и в графе (1.11) являются следующие суммы величин деревьев (1.12):
(см. скан)
а определитель этого графа равен сумме трех базовых определителей:
Начальная квазистадионарная скорость ферментативной реакции выражается через определители графа реакции следующим образом:
где константа скорости образования или связывания продукта узлом базовый определитель узла полная концентрация фермента. При вычислении в случае обратимого образования продукта используется следующее соглашение о знаках: если узел выбрасывает продукт, и если узел связывает продукт.
Например, для графа (1.11) по формуле (1.14) следует записать
Первый член в числителе положителен, так как распад освобождает а второй член отрицателен, так как связывается с
Квазистационарные концентрации промежуточных комплексов находятся по формуле
Так, в графе (1.11) концентрации свободного фермента и комплексов определяются выражениями
Между элементами множества вершин и множества ребер определено отношение инцидентности. Говорят, что ребро е инцидентно вершинам v1, v2, если оно соединяет эти вершины и наоборот, каждая из вершин v1, v2 инцидентна ребру е.
Рассмотрим графическое представление графов таблица 1.
Таблица 1. Графическое представление графов
Многие результаты, полученные для простых графов, без труда модно перенести на более общие объекты, в которых две вершины могут быть соединены более чем одним ребром. Кроме того, часто бывает удобно снять ограничение, состоящее в том, что ребро должно соединять две различные вершины, и допустить существование петель. Получающийся при этом объект, в котором могут быть и кратные ребра и петли называется графом (псевдографом). Псевдограф без петель называется мультиграфом
Рассмотрим некоторые важные типы графов.
Определение. Граф, у которого множество ребер пусто, называется вполне несвязным (или пустым) графом. Вполне несвязный граф обозначают N
Заметим, что у вполне несвязного графа все вершины изолированы
Определение. Простой граф, в котором любые две вершины смежны, называется полным. Полный граф обозначают K
Заметим, что для полного графа выполняется равенство
где m - число ребер, n - число вершин графа.
Определение. Граф, у которого все вершины имеют одну и ту же локальную степень n, называется регулярным (или однородным) степени n.
Регулярные графы степени 3 называются кубическими (или трехвалентными).
Известным примером кубического графа является граф Петерсона
Среди регулярных графов особенно интересны так называемые платоновы графы - графы, образованные вершинами и ребрами пяти правильных многогранников - Платоновых тел: тетраэдра, куба, октаэдра, додекаэдра и икосаэдра.На рисунке 6 приведен граф, соответствующий кубу.
Определение. Допустим, что множество вершин графа G можно разбить на два непересекающихся подмножества V1 и V2 так, что каждое ребро в G соединяет какую-нибудь вершину из V1 с какой-нибудь вершиной из V2, тогда данный граф называется двудольным.
Двудольный граф можно определить и по-другому - в терминах раскраски его вершин двумя цветами, скажем красным и синим. При этом граф называется двудольным, если каждую его вершину можно окрасить красным или синим цветом так, чтобы каждое ребро имело один конец красный, а другой - синий.
Определение. Если в двудольном графе каждая вершина из V1 соединена с каждой вершиной из V2, то граф называется полным двудольным.
Заметим, что граф Кm. n имеет ровно m + n вершин и mn ребер.
Определение. Объединением графов
называется граф
Определение. Пересечением графов
называется граф
Определение. Соединением графов G1 и G2 является новый граф, у которого
а множеством ребер являются все ребра первого и второго графа и ребра, соединяющие между собой каждую вершину первого графа с первой вершиной второго графа.
Определение. Граф называется связным, если его нельзя представить в виде объединения двух графов, и несвязным в противном случае.
Очевидно, что всякий несвязный граф можно представить в виде объединения конечного числа связных графов - каждый из таких связных графов называется компонентой связности графа.
Определение. Связный регулярный граф степени 2 называется циклическим графом. Обозначается Сn .
Определение. Соединение графов N1 и Cn-1 (n3) называется колесом с n вершинами. Обозначается Wn (рисунок 10)
Определение. Дополнением простого графа G называется простой граф с множеством вершин V(G), в котором две вершины смежны тогда и только тогда, когда они не смежны в исходном графе.
Обозначение. Другими словами, дополнением графа является граф, содержащий все вершины исходного графа и только те ребра, которых не хватает исходному графу для того, чтобы он стал полным.
Определение. Подграфом графа G называется граф, все вершины и ребра которого содержатся среди вершин и ребер графа G. Подграф называется собственным, если он отличен от самого графа.
Текст работы размещён без изображений и формул.
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
«В математике следует помнить не формулы, а процесс мышления…»
Е. И. Игнатьев
Теория графов в настоящее время является интенсивно развивающимся разделом математики. Это объясняется тем, что в виде графовых моделей описываются многие объекты и ситуации, что очень важно для нормального функционирования общественной жизни. Именно этот фактор определяет актуальность их более подробного изучения. Поэтому тематика данной работы достаточно актуальна.
Цель исследовательской работы: выяснить особенности применения теории графов в различных областях знаний и при решении логических задач.
Цель определила следующие задачи:
познакомиться с историей теории графов;
изучить основные понятия теории графов и основные характеристики графов;
показать практическое применение теории графов в различных областях знаний;
рассмотреть способы решения задач с помощью графов и составить собственные задачи.
Объект исследования: сфера деятельности человека на предмет применения метода графов.
Предмет исследования: раздел математики «Теория графов».
Гипотеза. Мы предполагаем, что изучение теории графов может помочь учащимся решать логические задачи по математике, что определит их дальнейшие интересы.
Методы исследовательской работы:
В ходе нашего исследования были использованы такие методы, как:
1) Работа с различными источниками информации.
2) Описание, сбор, систематизация материала.
3) Наблюдение, анализ и сравнение.
4) Составление задач.
Теоретическая и практическая значимость данной работы определяется тем, что результаты могут быть использованы на информатике, математике, геометрии, черчении и классных часах, а также для широкого круга читателей, заинтересованных данной темой. Исследовательская работа имеет выраженную практическую направленность, так как в работе автором представлены многочисленные примеры применения графов во многих областях знаний, составлены свои задачи. Данный материал можно использовать на факультативных занятиях по математике.
ГЛАВА I. ТЕОРЕТИЧЕСКИЙ ОБЗОР МАТЕРИАЛА ПО ТЕМЕ ИССЛЕДОВАНИЯ
Теория графов. Основные понятия
В математике «граф» можно изобразить в виде картинки, которая представляет собой некоторое количество точек, соединенных линиями. «Граф» происходит от латинского слова «графио» - пишу, как и известный дворянский титул.
В математике определение графа дается так:
Термин «граф» в математике определяется следующим образом:
Граф - это конечное множество точек - вершин , которые могут быть соединены линиями - ребрами .
В качестве примеров графов могут выступать чертежи многоугольников, электросхемы, схематичное изображение авиалиний, метро, дорог и т.п. Генеалогическое дерево также является графом, где вершинами служат члены рода, а родственные связи выступают в качестве ребер графа.
Рис. 1 Примеры графов
Число ребер, которое принадлежит одной вершине, называется степенью вершины графа . Если степень вершины нечетное число, вершина называется - нечетной . Если степень вершины число четное, то и вершина называется четной .
Рис. 2 Вершина графа
Нуль-граф - это граф, состоящий только из изолированных вершин, не соединенных ребрами.
Полный граф - это граф, каждая пара вершин которого соединена ребром. N-угольник, в котором проведены все диагонали, может служить примеров полного графа.
Если в графе выбрать такой путь, когда начальная и конечная точка совпадают, то такой путь называется циклом графа . Если прохождение через каждую вершину графа происходит не более одного раза, то цикл называется простым .
Если в графе каждые две вершины связаны ребром, то это связанный граф. Граф называется несвязанным , если в нем есть хотя бы одна пара несвязанных вершин.
Если граф связанный, но не содержит циклов, то такой граф называетсядеревом .
Характеристики графов
Путь графа - это такая последовательность, в которой каждые два соседних ребра, имеющих одну общую вершину, встречаются только один раз.
Длина кратчайшей цепи из вершин a и b называется расстоянием между вершинами a и b.
Вершина а называется центром графа, если расстояние между вершиной а и любой другой вершиной является наименьшим и из возможных. Такое расстояние есть радиус графа.
Максимально возможное расстояние между двумя любыми вершинами графа называется диаметром графа.
Раскраска графов и применение.
Если внимательно посмотреть на географическую карту, то можно увидеть железные или шоссейные дороги, которые являются графами. Кроме этого на катре есть граф, который состоит из границ между странами (районами, областями).
В 1852 году английскому студенту Френсису Гутри поставили задачу раскрасить карту Великобритани, выделив каждое графство отдельным цветом. Из-за небольшого выбора красок Гутри использовал их повторно. Он подбирал цвета так, чтобы те графства, которые имеют общий участок границы, обязательно окрашивались в разные цвета. Возник вопрос, какое наименьшее количество красок необходимо для раскрашивания различных карт. Френсис Гутри предположил, хотя и не смог доказать, что четырех цветов будет достаточно. Эта проблема бурно обсуждалась в студенческих кругах, но позже была забыта.
«Проблема четырех красок» вызывала все больший интерес, но так и не была решена, даже выдающимися математиками. В 1890 году английским математиком Перси Хивудом было доказано, что для раскрашивания любой карты будет достаточно пяти красок. А только 1968 году смогли доказать, что для раскрашивания карты, на которой изображено меньше сорока стран, будет достаточно 4 цветов.
В 1976 году эта задача была решена при использовании компьютера двумя американскими математиками Кеннетом Аппелем и Вольфгантом Хакеном. Для ее решения все карты были поделены на 2000 типов. Для компьютера была создана программа, которая исследовала все типы с целью выяления таких карт, для раскрашивания которых будет недостаточно четырех красок. Только три типа карт компьютер исследовать не смог, поэтому математики изучали их самостоятельно. В результате было установлено, что для раскрашивания всех 2000 типов карт будет достаточно 4 красок. Им было объявлено о решении проблемы четырех красок. В этот день почтовое отделение при университете, в котором работали Аппель и Хакен на всех марках ставило штемпель со словами: «Четырех красок достаточно».
Можно представить задачу о четырех красках несколько иначе.
Для этого рассмотрим произвольную карту, представив ее виде графа: столицы государств являются вершинами графа, а ребра графа связывают те вершины (столицы), государства которых имеют общую границу. Для получения такого графа формулируется следующая задача - необходимо раскрасить граф с помощью четырех цветов так, чтобы вершины, имеющие общее ребро были раскрашены разными цветами.
Эйлеровы и Гамильтоновы графы
В 1859 году английским математиком Уильямом Гамильтоном была выпущена в продажу головоломка - деревянный додекаэдр (двенадцатигранник), двадцать вершин которого были обозначены гвоздиками. Каждая вершина имела название одного из крупнейших городов мира - Кантон, Дели, Брюссель, и т.д. Задача заключалась в нахождении замкнутого пути, который проходит по ребрам многогранника, побывав в каждой вершине только один раз. Для отмечания пути использовался шнур, который цепляли за гвоздики.
Гамильтоновым циклом называется граф, путь которого является простым циклом, который проходит через все вершины графа по одному разу.
На реке Прегель расположен город Калининград (бывший Кенигсберг). Река омывала два острова, которые между собой и с берегами были соединены мостами. Старых мостов сейчас уже нет. Память о них осталась только на карте города.
Однажды один житель города спросил у своего знакомого, можно ли пройти по всем мостам, побывать на каждом только один раз и вернуться к тому месту откуда началась прогулка. Эта задача заинтересовала многих горожан, но решить ее никто не смог. Этот вопрос вызвал заинтересованность ученных многих стран. Решение проблемы получил математик Леонард Эйлер. Кроме этого он сформулировал общий подход к решению таких задач. Для этого он превратил карту в граф. Вершинами этого графа стала суша, а ребрами - мосты, ее соединяющие.
При решении задачи про мосты Кенигсберга Эйлеру удалось сформулировать свойства графов.
Начертить граф, начав движение с одной вершины и окончив в той же вершине одним росчерком (дважды не проводя по одной и той же линии и не отрывая карандаша от бумаги) возможно в том случае, если все вершины графа четные.
Если есть граф с двумя нечетными вершинами, то его вершины тоже можно соединить одним росчерком. Для этого нужно начать с одной, а закончить на другой любой нечетной вершине.
Если есть граф с числом нечетных вершин больше двух, то граф невозможно начертить одним росчерком.
Если применять эти свойства на задачу о мостах, то можно увидеть, что все вершины исследуемого графа нечетные, значит, этот граф нельзя соединить одним росчерком, т.е. невозможно пройти по всем мостам один раз и закончить путь в том месте, где он был начат.
Если граф имеет цикл (не обязательно простой), содержащий все рѐбра графа по одному разу, то такой цикл называется Эйлеровым циклом . Эйлерова цепь (путь, цикл, контур) — цепь (путь, цикл, контур), содержащая все рѐбра (дуги) графа по одному разу.
ГЛАВА II. ОПИСАНИЕ ИССЛЕДОВАНИЯ И ЕГО РЕЗУЛЬТАТЫ
2.1. Этапы проведения исследования
Для проверки гипотезы исследование включало три этапа (таблица 1):
Этапы исследования
Таблица 1.
|
Используемые методы |
|||
|
Теоретическое исследование проблемы |
Изучить и проанализировать познавательную и научную литературу. |
самостоятельное размышление; изучение информационных источников; поиск необходимой литературы. |
|
|
Практическое исследование проблемы |
Рассмотреть и проанализировать области практического применения графов; |
наблюдение; анализ; сравнение; анкетирование. |
|
|
3 этап. Практическое использование результатов |
Обобщить изученную информацию; |
систематизация; отчет (устный, письменный, с демонстрацией материалов) |
сентябрь 2017 г. |
2.2. Области практического применения графов
Графы и информация
Теория информации широко использует свойства двоичных деревьев.
Например, если нужно закодировать некоторое число сообщений в виде определенных последовательностей нулей и единиц различной длины. Код считается наилучшим, для заданной вероятности кодовых слов, если средняя длина слов наименьшая в сравнении другими распределениями вероятности. Для решения такой задачи Хаффман предложил алгоритм, в котором, код представляется деревом-графом в рамках теории поиска. Для каждой вершины предлагается вопрос, ответом на который может быть либо, «да», либо «нет» - что соответствует двум ребрам, выходящим из вершины. Построение такого дерева завершается после установления того, что требовалось. Это может применяться в интервьюировании нескольких человек, когда заранее неизвестен ответ на предыдущий вопрос, план интервью представляется в виде двоичного дерева.
Графы и химия
Еще А. Кэли рассмотрел задачу о возможных структурах насыщенных (или предельных) углеводородов, молекулы которых задаются формулой:
CnH 2n+2
Все атомы углеводорода 4-хвалентны, все атомы водорода 1-валентны. Структурные формулы простейших углеводородов показаны на рисунке.
Каждую молекулу предельного углеводорода можно представить в виде дерева. При удалении всех атомов водорода, атомы углеводорода, которые остались, образуют дерево с вершинами, степень которых не выше четырех. Значит, количество возможных искомых структур (гомологов данного вещества) равняется числу деревьев, степени вершин которых, не больше 4. Это задача сводится к задаче о перечислении деревьев отдельного вида. Д. Пойа рассмотрел эту задачу и ее обобщения.
Графы и биология
Процесс размножения бактерий - это одна из разновидностей ветвящихся процессов, встречающихся в биологической теории. Пусть каждая бактерия по истечению определенного времени или погибает, или делится на две. Следовательно, для одной бактерии мы получим двоичное дерево размножения ее потомства. Вопрос задачи заключается в следующем, какое количество случаев содержит k потомков в n-м поколение одной бактерии? Данное соотношение в биологии носит название процесс Гальтона-Ватсона, которое обозначает необходимое количество нужных случаев.
Графы и физика
Сложная утомительная задача для любого радиолюбителя - создание печатных схем (пластина диэлектрика - изолирующего материала и вытравленные дорожки в виде металлических полосок). Пересечение дорожек происходит только в определенных точках (местах установления триодов, резисторов, диодов и пр.) по определенным правилам. В результате перед ученым стоит задача вычертить плоский граф, с вершинами в
Итак, все выше сказанное подтверждает практическую ценность графов.
Математика интернета
Интернет - всемирная система объединенных компьютерных сетей для хранения и передачи информации.
Сеть интернет можно представить в виде графа, где вершины графа - это интернет сайты, а ребра - это ссылки (гиперссылки), идущие с одних сайтов на другие.
Веб-граф (Интернет), имеющий миллиарды вершин и ребер, постоянно меняется - спонтанно добавляются и исчезают сайты, пропадают и добавляются ссылки. Однако, Интернет имеет математическую структуру, подчиняется теории графов и имеет несколько «устойчивых» свойств.
Веб-граф разрежен. Он содержит всего лишь в несколько раз больше ребер, чем вершин.
Несмотря на разреженность, интернет очень тесен. От одного сайта до другого по ссылкам, можно перейти за 5 - 6 кликов (знаменитая теория «шести рукопожатий»).
Как мы знаем, степень графа - это число ребер, которым принадлежит вершина. Степени вершин веб-графа распределены по определенному закону: доля сайтов (вершин) с большим количеством ссылок (ребер) мала, а сайтов с малым количеством ссылок - велика. Математически это можно записать так:
где - доля вершин определенной степени, - степень вершины, - постоянная, независящая от числа вершин веб-графа, т.е. не меняется в процессе добавления или удаления сайтов (вершин).
Этот степенной закон является универсальным для сложных сетей - от биологических до межбанковских.
Интернет как целое устойчив к случайным атакам на сайты.
Так как уничтожение и создание сайтов происходит независимо и с одинаковой вероятностью, то и веб-граф, с вероятность близкой к 1, сохраняет свою целостность и не разрушается.
Для изучения интернета необходимо строить модель случайного графа. Эта модель должна обладать свойствами реального интернета и не должна быть слишком сложной.
Эта задача пока полностью не решена! Решение этой задачи - построения качественной модели интернета - позволит разработать новые инструменты для улучшения поиска информации, выявления спама, распространения информации.
Построение биологических и экономических моделей началось значительно раньше, чем возникла задача построения математической модели интернета. Однако достижения в развитии и изучении интернета, позволили ответить на многие вопросы, касающиеся всех этих моделей.
Математика интернета востребована многими специалистами: биологами (предсказание роста популяций бактерий), финансистами (риски возникновения кризисов) и т.п. Изучение подобных систем - один из центральных разделов прикладной математики и информатики.
г. Мурманск с помощью графа.
Когда человек приезжает в новый для него город, как правило, первое желание - это посетить главные достопримечательности. Но при этом запас времени зачастую ограничен, а в случае деловой поездки, совсем мал. Следовательно, необходимо планировать знакомство с достопримечательностями заранее. И в построении маршрута отлично помогут графы!
В качестве примера рассмотрим типичный случай прибытия в Мурманск из аэропорта в первый раз. Планируется посетить следующие достопримечательности:
1. Морской православный храм Спас-на-водах;
2. Свято-Никольский собор;
3. Океанариум;
4. Памятник коту Семену;
5. Атомный ледокол Ленин;
6. Парк Огни Мурманска;
7. Парк Долина Уюта;
8. Кольский мост;
9. Музей истории Мурманского морского пароходства;
10. Площадь Пяти углов;
11. Морской торговый порт
Вначале расположим эти места на карте и получим наглядное представление о местоположении и расстоянии между достопримечательностями. Сеть дорог достаточно развита, и перемещение на автомобиле не будет затруднительным.
Достопримечательности на карте (слева) и полученный граф (справа) показаны на соответствующем рисунке ПРИЛОЖЕНИЯ №1. Таким образом, новоприбывший вначале проедет около Кольского моста(и, при желании может пересечь его туда - обратно); затем отдохнет в Парке Огни Мурманска и Долине Уюта и отправится дальше. В итоге оптимальный маршрут составит:
С помощью графа можно также визуализировать схему проведения соцопросов. Примеры представлены в ПРИЛОЖЕНИИ №2. В зависимости от данных ответов опрашиваемому задают разные вопросы. Например, если в социологическом опросе №1 опрашиваемый считает математику важнейшей из наук, у него спросят, уверенно ли он чувствует себя на уроках физики; если же он считает иначе, второй вопрос будет касаться востребованности гуманитарных наук. Вершинами такого графа являются вопросы, а ребрами - варианты ответов.
2.3. Применение теории графов при решении задач
Теория графов применяется при решении задач из многих предметных областей: математика, биология, информатика. Мы изучили принцип решения задач с помощью теории графов и составили собственные задачи по теме исследования.
Задача №1.
Пятеро одноклассников, на встрече выпускников, обменялись рукопожатиями. Сколько всего было сделано рукопожатий?
Решение: Обозначим одноклассников вершинами графа. Соединим каждую вершину линиями, с четырьмя другими вершинам. Получаем 10 линий, это и есть рукопожатиями.
Ответ: 10 рукопожатий (каждая линия означает одно рукопожатие).
Задача №2.
У моей бабушке в деревне, возле дома растут 8 деревьев: тополь, дуб, клен, яблоня, лиственница, береза, рябина и сосна. Рябина выше лиственницы, яблоня выше клена, дуб ниже березы, но выше сосны, сосна выше рябины, береза ниже тополя, а лиственница выше яблони. В какой последовательности расположатся деревья по высоте от самого высокого к самому низкому.
Решение:
Деревья - это вершины графа. Обозначим их первой буквой в кружочке. Проведем стрелки от низкого дерева к более высокому. Сказано, что рябина выше лиственницы, то стрелку ставим от лиственницы к рябине, берёза ниже тополя, то стрелку ставим от тополя к берёзе и т.п. Получаем граф, где видно, что самое низкое дерево - клен, потом яблоня, лиственница, рябина, сосна, дуб, береза и тополь.
Ответ: клен, яблоня, лиственница, рябина, сосна, дуб, береза и тополь.
Задача №3.
У Мамы есть 2 конверта: обычный и авиа, и 3 марки: квадратная, прямоугольная и треугольная. Сколькими способами Мама может выбрать конверт и марку, чтобы отправить письмо Папе?
Ответ: 6 способов
Задача №4.
Между населенными пунктами A, B, C, D, E построены дороги. Нужно определить длину кратчайшего пути между пунктами А и Е. Передвигаться можно только по дорогам, длина которых указана на рисунке.
Задача №5.
Тремя одноклассника - Максим, Кирилл и Вова решили заняться спортом и прошли отбор спортивные секции. Известно, что в баскетбольную секцию претендовал 1 мальчик, а в хоккей хотели играть трое. Максим пробовался только в 1 секцию, Кирилл отбирался во все три секции, а Вова в 2. Кого из мальчиков в какую спортивную секцию отобрали?
Решение: Для решения задачи применим графы
Баскетбол Максим
Футбол Кирилл
Хоккей Вова
Так как к баскетболу идет лишь одна стрелка, то Кирилла отобрали в сецию баскетбола . Тогда Кирилл не будет играть в хоккей , а значит, в хоккейную секцию отобрали Максима, который пробовался только в эту секцию, тогда Вова будет футболистом .
Задача №6.
Из-за болезни некоторых преподавателей, завучу школы, требуется составить фрагмент расписания занятий в школе хотя бы на один день, с учетом следующих обстоятельств:
1. Преподаватель ОБЖ согласен дать только последний урок;
2. Преподаватель географии может дать либо второй, либо третий урок;
3. Математик готов дать либо только первый, либо только второй урок;
4. Преподаватель физики может дать либо первый, либо второй, либо третий уроки, но только в одном классе.
Какое расписание может составить завуч школы, чтобы оно удовлетворяло всем преподавателей?
Решение: Эту задачу можно решить перебирая все возможные варианты, но проще, если начертить граф.
1. 1) физика 2. 1) математика 3. 1) математика
2) математика 2) физика 2) география
3) география 3) география 3) физика
4) ОБЖ 4) ОБЖ 4) ОБЖ
Заключение
В данной исследовательской работе была подробно изучена теория графов, доказана гипотеза, что изучение графов может помочь в решении логических задач, кроме того, рассмотрена теорию графов в разных областях науки и составлены свои 7 задач.
Использование графов при обучении обучающихся поиску решения задач позволяет совершенствовать графические умения учащихся и связывать рассуждения специальным языком конечного множества точек, некоторые из которых соединены линиями. Все это способствует проведению работы по обучению учащихся мышлению.
Эффективность учебной деятельности по развитию мышления во многом зависит от степени творческой активности учащихся при решении математических задач. Следовательно, необходимы математические задачи и упражнения, которые бы активизировали мыслительную деятельность школьников.
Применение задач и использованием элементов теории графов на факультативных занятиях в школе как раз и преследует цель активизации мыслительной деятельности учащихся. Мы считаем, что практический материал по нашему исследованию может быть полезен на факультативных занятиях по математике.
Таким образом, цель исследовательской работы достигнута, задачи решены. В перспективе мы планируем продолжить изучение теории графов и разработать свои маршруты, например, с помощью графа создать экскурсионный маршрут для школьного автобуса ЗАТО Александровск по музеям и памятным местам г. Мурманска.
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ
Березина Л. Ю. «Графы и их применение» - М.: «Просвещение», 1979
Гарднер М. «Математические досуги», М. «Мир», 1972
Гарднер М. «Математические головоломки и развлечения», М. «Мир», 1971
Горбачев А. «Сборник олимпиадных задач» - М. МЦНМО, 2005
Зыков А. А. Основы теории графов. — М.: «Вузовская книга», 2004. — С. 664
Касаткин В. Н. «Необычные задачи математики», Киев, «Радяньска школа», 1987
Математическая составляющая / Редакторы-составители Н.Н. Андреев, С.П. Коновалов, Н.М. Панюшкин. - М.: Фонд «Математические этюды» 2015 г. - 151 с.
Мельников О. И. «Занимательные задачи по теории графов», Мн. «ТетраСистемс»,2001
Мельников О.И. Незнайка в стране графов: Пособие для учащихся. Изд. 3-е, стереотипное. М.: КомКнига, 2007. — 160 с.
Олехник С. Н., Нестеренко Ю. В., Потапов М. К. «Старинные занимательные задачи», М. «Наука», 1988
Оре О. «Графы и их применения», М. «Мир», 1965
Харари Ф. Теория графов / Пер.с англ. и предисл. В. П. Козырева. Под ред. Г. П. Гаврилова. Изд. 2-е. - М.: Едиториал УРСС, 2003. - 296 с.
ПРИЛОЖЕНИЕ №1
Составление оптимального маршрута посещения главных достопримечательностей
г. Мурманск с помощью графа.
Оптимальный маршрут составит:
8. Кольский мост6. Парк Огни Мурманска7. Парк Долина Уюта2. Свято-Никольский собор10. Площадь Пяти углов5. Атомный ледокол Ленин9. Музей истории Мурманского морского пароходства11. Морской торговый порт1. Морской православный храм Спас-на-водах4. Памятник коту Семену3. Океанариум.
ПУТЕВОДИТЕЛЬ ПО ДОСТОПРИМЕЧАТЕЛЬНОСТЯМ МУРМАНСКА
ПРИЛОЖЕНИЕ №2
Социологические опросы № 1, 2
Как оказалось тема алгоритмов интересна Хабра-сообществу. Поэтому я как и обещал, начну серию обзоров «классических» алгоритмов на графах.Так как публика на Хабре разная, а тема интересна многим, я должен начать с нулевой части. В этой части я расскажу что такое граф, как он представлен в компьютере и зачем он используется. Заранее прошу прощения у тех кто это все уже прекрасно знает, но для того чтобы объяснять алгоритмы на графах, нужно сначала объяснить что такое граф. Без этого никак.
Основы
В математике, Граф - это абстрактное представление множества объектов и связей между ними. Графом называют пару (V, E) где V это множество вершин , а E множество пар, каждая из которых представляет собой связь (эти пары называют рёбрами ).Граф может быть ориентированным или неориентированным . В ориентированном графе, связи являются направленными (то есть пары в E являются упорядоченными, например пары (a, b) и (b, a) это две разные связи). В свою очередь в неориентированном графе, связи ненаправленные, и поэтому если существует связь (a, b) то значит что существует связь (b, a).
Пример:
Неориентированный граф: Соседство (в жизни). Если (1) сосед (3), то (3) сосед (1). См рис. 1.а
Степень
вершины может быть входящая и исходящая (для неориентированных графов входящая степень равна исходящей).
Входящая степень вершины v это количество ребер вида (i, v
), то есть количество ребер которые «входят» в v.
Исходящая степень вершины v это количество ребер вида (v
, i), то есть количество ребер которые «выходят» из v.
Это не совсем формальное определение (более формально определение через инцидентность), но оно вполне отражает суть
Путь в графе это конечная последовательность вершин, в которой каждые две вершины идущие подряд соединены ребром. Путь может быть ориентированным или неориентированным в зависимости от графа. На рис 1.а, путем является например последовательность [(1), (4), (5)] на рис 1.б, [(1), (3), (4), (5)].
У графов есть ещё много разных свойств (например они могут быть связными, двудольными, полными), но я не буду описывать все эти свойства сейчас, а в следующих частях когда эти понятия понадобятся нам.
Представление графов
Существует два способа представления графа, в виде списков смежности и в виде матрицы смежности. Оба способа подходят для представления ориентированных и неориентированных графов.Матрица смежности
Этот способ является удобным для представления плотных
графов, в которых количество рёбер (|E|) примерно равно количеству вершин в квадрате (|V| 2).
В данном представлении мы заполняем матрицу размером |V| x |V| следущим образом:
A[i][j] = 1 (Если существует ребро из i в j)
A[i][j] = 0 (Иначе)
Данный способ подходит для ориентированных и неориентированных графов. Для неориентированных графов матрица A является симметричной (то есть A[i][j] == A[j][i], т.к. если существует ребро между i и j, то оно является и ребром из i в j, и ребром из j в i). Благодаря этому свойству можно сократить почти в два раза использование памяти, храня элементы только в верхней части матрицы, над главной диагональю)
Понятно что с помощью данного способа представления, можно быстро проверить есть ли ребро между вершинами v и u, просто посмотрев в ячейку A[v][u].
С другой стороны этот способ очень громоздкий, так как требует O (|V| 2) памяти для хранения матрицы.
На рис. 2 приведены представления графов из рис. 1 с помощью матриц смежности.
Списки смежности
Данный способ представления больше подходит для разреженных графов, то есть графов у которых количество рёбер гораздо меньше чем количество вершин в квадрате (|E| << |V| 2).
В данном представлении используется массив Adj содержащий |V| списков. В каждом списке Adj[v] содержатся все вершины u, так что между v и u есть ребро. Память требуемая для представления равна O (|E| + |V|) что является лучшим показателем чем матрица смежности для разреженных графов.
Главный недостаток этого способа представления в том, что нет быстрого способа проверить существует ли ребро (u, v).
На рис. 3 приведены представления графов из рис. 1 с помощью списков смежности.
Применение
Те кто дочитал до этого места, наверное задали себе вопрос, а где же собственно я смогу применить графы. Как я и обещал я буду стараться приводить примеры. Самый первый пример который приходит в голову это социальная сеть. Вершинами графа являются люди, а ребрами отношения (дружба). Граф может быть неориентированным, то есть я могу дружить только с теми кто дружит со мной. Либо ориентированным (как например в ЖЖ), где можно добавить человека в друзья, без того чтобы он добавлял вас. Если же он да добавит вас вы будете «взаимными друзьями». То есть будет существовать два ребра: (Он, Вы) и (Вы, Он)Ещё одно из применений графа, которое я уже упоминал это ссылки с сайта на сайт. Представим Вы хотите сделать поисковую систему и хотите учесть на какие сайты есть больше ссылок (например сайт A), при этом учитывать сколько сайтов ссылается на сайт B, который ссылается на сайт A. У вас будет матрица смежности этих ссылок. Вы захотите ввести какую то систему подсчёта рейтинга, которая делает какие то подсчёты на этой матрице, ну, а дальше… это Google (точнее PageRank) =)