НОУ " Теория графов"

Выступление

     Данная тема актуальна, потому что Быстрое развитие современных вычислительных систем сделало возможным возникновение целых отраслей математики, ориентированных в первую очередь на обработку больших массивов информации и решение с помощью компьютера многих прикладных задач из различных областей науки, которые могут быть формализованы и сведены к математическим задачам. Одной из подобных отраслей, без сомнения, является теория графов, язык которой настолько гибок и совершенен, что позволяет описать практически любую формальную систему условий, -- порой даже более точно, чем  классические разделы математики, такие, как алгебра и дифференциально-интегральное исчисление. Являясь одной из самых молодых математических дисциплин, теория графов в настоящее время переживает период бурного роста и развития.
     Данное исследование посвящено в основном описанию базовых понятий и методов теории графов и тому, как они могут быть использованы в сведении к математическим многих проблем естественных наук, включая физику, химию, биологию, медицину, социологию.
     Родоначальником теории графов считается Леонард Эйлер. Родился в 1707 году в Швейцарии.  Оставил важнейшие труды по самым различным отраслям математики, механики, физики, астрономии и по ряду прикладных наук. 13 марта 1796 года Эйлер в письме итальянскому математику и инженеру  Джованни Джакобо Маринони приводит правило для решения задачи «о семи мостах Кенигсберга», пользуясь которым, легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них. В данном случае ответ был: «нельзя».
     Семь мостов Кенигсберга - старинная математическая задача, в которой спрашивалось, как можно пройти по всем семи мостам Кёнигсберга, не проходя ни по одному из них дважды. 
     Теория графов– дисциплина математическая, созданная усилиями математиков, поэтому ее изложение включает в себя много необходимых строгих определений.
     Граф – математический объект, совокупность объектов соединенных между собой связями. Иначе говоря, граф – это совокупность двух множеств: множества точек, которые называются вершинами, и множества ребер.  
     Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или рёбрах.
     Различают такие графы как: «дерево», ориентированный, неориентированный, смежный, взвешенный, эйлеров, полуэйлеров, мультигрф, гамильтонов, полный, нулевой графы.
    Существует много различных задач на теорию графов, одной из самых известных является «задача коммивояжера», заключающаяся в поиске самого выгодного маршрута, проходящего через некоторое количество вершин с последующим возвратом в исходную вершину.
    Многие типы задач на теорию графов можно встретить в ОГЭ и ЕГЭ. К примеру:

Задача 4: Для составления цепочек разрешается использовать бусины 5 типов, обозначаемых буквами  А, Б, В, Е, И. Каждая цепочка должна состоять из трех бусин, при этом должны соблюдаться следующие правила:

а) на первом месте стоит одна из букв: А, Е, И,

б) после гласной буквы в цепочке не может снова идти гласная, а после согласной – согласная,

в) последней буквой не может быть А.

Какая из цепочек построена по этим правилам?

1)АИБ                     2) ЕВА                  3) БИВ                 4) ИБИ

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

Применение графов имеет весьма широкую область. К примеру:
      Графы в теории массового обслуживания для оптимального размещения пунктов массового обслуживания, таких как больницы, сберегательные банки, пожарные части, почтамты и т.п.,
     Графы в математике для решения логических задач и головоломок.
     Графы в физике для конструирования различных типов электро-схем.
     Графы в психологии для представления промежуточных и окончательных результатов теоретических и экспериментальных исследований.
     Графы в логистике для анализа логических систем.
     В химии для решения теоретических задач. Химические графы дают возможность прогнозировать химические превращения, пояснять сущность и систематизировать некоторые основные понятия химии.  К химическим графам относятся молекулярные, двудольные и сигнальные графы кинетических уравнений реакций.
      Для решения многомерных задач анализа и оптимизации химико-технологических систем (ХТС) используют следующие химико-технологические графы: потоковые, информационно-потоковые, сигнальные и графы надежности.
     В биологии и медицине, т. к. Болезнь можно описать, как  взаимодействие процессов на молекулярном уровне. Взаимосвязи в интерактоме —  многослойной сетевой структуре, включающей в себя все процессы в живой клетке: от сети взаимодействий белок-белок до регуляторных сетей и сетей метаболических реакций.

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

1)     Формализация и построение общей структурной модели социального объекта на разных уровнях его сложности.

2)     Анализ полученной модели, выделение в ней структурных единиц (подсистем) и изучение их связей.

3)     Изучение уровней структуры иерархических организаций: количество уровней, количество связей, идущих из одного уровня в другой и от одного лица к другому. а) количественной оценки веса (статуса) индивида в иерархической организации.
б) определение лидера группы.

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

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

    Многие задачи теории графов являются так называемыми NP-полными задачами, поиск эффективных (то есть требующих не более полиномиального количества элементарных операций) решений которых представляет одну из центральных и самых волнующих проблем современной математики и даже всей науки в целом.
     Гамильто́нов граф — граф (набор точек и соединяющих их линий), который содержит гамильтонов цикл. Гамильтоновым циклом является такой цикл (замкнутый путь), который проходит через каждую вершину данного графа ровно по одному разу.  С гамильтоновым графом тесно связано понятие гамильтонова пути, который является простым путём (путём без петель), проходящим через каждую вершину графа ровно один раз. Гамильтонов путь отличается от цикла тем, что у пути начальные и конечные точки могут не совпадать, в отличие от цикла. Гамильтонов цикл является гамильтоновым путём.

Цвет глаз —характеристика, определяемая пигментацией радужной оболочки. Традиционно полагается, что цвет глаз определяется наследственностью.
Согласно классической генетике, гены, дающие тёмные глаза, — доминантные, а светлые — рецессивные. Однако в действительности генетика цвета глаз очень сложна, поэтому их комбинации у родителей и детей могут быть крайне разнообразны.

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

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

• 1 слайд

  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
   
   
   
   
  Теория Графов и ее применение в науке
   
   
    
   
   
   
  
  
  
  
  
  
  
  
  
  

• 2 слайд

  История Графов
  Родоначальником теории графов считается
  Леонард Эйлер(1707гр).
  Оставил важнейшие труды в отраслях:
  Математика
  Механика
  Физика
  Астрономия
  Прикладные науки
  
  

• 3 слайд

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

• 4 слайд

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

• 5 слайд

  «Дерево»
  Ориентированный
  Неориентированный
  Эйлеров
  Полуэйлеров
  Гамильтонов
  Виды графов
  

• 6 слайд

  Задачи на Теорию графов
  Задача Коммивояжера
  
  Это оптимальный маршрут коммивояжёра через 15 крупнейших городов Германии. Указанный маршрут является самым коротким из всех возможных 43 589 145 600 вариантов.
  

• 7 слайд

  Задачи ОГЭ и ЕГЭ
  Для составления цепочек разрешается использовать бусины 5 типов, обозначаемых буквами А, Б, В, Е, И. Каждая цепочка должна состоять из трех бусин, при этом должны соблюдаться следующие правила:
  а) на первом месте стоит одна из букв: А, Е, И,
  б) после гласной буквы в цепочке не может снова идти гласная, а после согласной – согласная,
  в) последней буквой не может быть А.
  Какая из цепочек построена по этим правилам?
  1)АИБ2) ЕВА3) БИВ4) ИБИ
  
  Решение:
  
  
  Е
  И
  Е
  И
  Е
  И
  Е
  И
  Е
  И
  Е
  В
  А
  Б
  И
  В
  Б
  В
  Б
  Е
  И
  Представив решение графически с помощью графа-дерева, легко посчитать, что число возможных вариантов – 12.
  
  

• 8 слайд

  Необходимо составить фрагмент расписания для одного дня занятий с учетом следующих обстоятельств:
  учитель истории может дать либо первый, либо второй, либо третий уроки, но только один урок:
  учитель литературы может дать один, либо второй, либо третий урок;
  математик готов дать либо только первый, либо только второй урок;
  Преподаватель физкультуры может дать только последний урок.
  Сколько можно составить вариантов расписания так, чтобы оно устроило всех учителей? (Обозначения: М – математика, Ф – физкультура, И – история, Л – литература)
  
  Л
  И
  и
  И
  Л
  М
  М
  М
  И
  Л
  Л
  И
  И
  Л
  И
  Л
  Ф
  Ф
  Ф
  Построим усеченный граф-дерево. Ветви, которые отсекаются на этапе построения, указаны красным цветом.
  Таким образом, из построенного графа видно, что расписание, которое устроит всех учителей, можно составить тремя способами
  

• 9 слайд

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

• 10 слайд

  Графы в физике для конструирования различных типов электро-схем.
  

• 11 слайд

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

• 12 слайд

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

• 13 слайд

  В биологии и медицине для описания различных болезней и структур биологических организмов.
  

• 14 слайд

  
  
  Типы социологических и социально-психологических задач, решаемых с помощью Теории графов
  Сети ДНК
  Проблема Гамильтонова пути
  
  
  
  
  
  

• 15 слайд

  Генетика цвета глаз
  
  Цвет глаз —характеристика, определяемая пигментацией радужной оболочки. Традиционно полагается, что цвет глаз определяется наследственностью.
  
   
  Шкала Бунака
  Тип 1. Тёмный.
  Вариант 1. Чёрный.
  Вариант 2. Тёмно-карий. Окраска равномерная.
  Вариант 3. Светло-карий. Окраска неравномерная.
  Вариант 4. Жёлтый. Очень редкий вариант.
  Тип 2. Переходный, смешанный.
  Вариант 5. Буро-жёлто-зелёный.
  Вариант 6. Зелёный.
  Вариант 7. Серо-зелёный.
  Вариант 8. Серый или голубой, вокруг зрачка — буро-жёлтое обрамление.
  Тип 3. Светлый.
  Вариант 9. Серый. Может быть разных оттенков.
  Вариант 10. Серо-голубой. Окраска неравномерная.
  Вариант 11. Голубой.
  Вариант 12. Синий. Встречается редко.
  

• 16 слайд

  Определение цвета глаз с помощью теории графов
  
  

• 17 слайд

  1)Качкин Николай Никифорович – голубые
  2)Качкина Наталья Михайловна – серо-зеленые
  3)Карасева Анна Матвеевна – серые
  4)Галай Григорий Алексеевич – серые
  5)Тарасова Мария Андреевна – карие
  6)Папа неизвестен
  7)Аралкин Алексей Максимович – карие
  8)Аралкина Мария Алексеевна - голубые
  9)Галай Нина Николаевна - зеленые
  10)Галай Юрий Григорьевич – серые с голубизной
  11)Тарасов Валерий Алексеевич - синий
  12)Тарасова Татьяна Алексеевна – серо-зеленый
  13)Галай Олег Юрьевич - золотисто-зеленые
  14)Галай Жанна Валерьевна – синие
  15)Галай Роман Олегович – серо-зеленые
  16)Галай Марк Олегович – серо-синие
  17)Галай Тимур Олегович – серо-зеленые
  1
  2
  9
  10
  13
  14
  11
  12
  16
  15
  17
  5
  6
  7
  8
  3
  4
  

• 18 слайд

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

• 19 слайд

  Спасибо за внимание!
  

Научное общество учащихся «Эврика»

Муниципальное Бюджетное Образовательное Учреждение
Лицей №8

Нижегородского района г. Н. Новгорода

Теория графов и ее применение в науке

Работу выполнил Ученик 9 «А» класса

Галай Роман

Научный Руководитель:

Дюпина Е.А.

Учитель математики

Нижний Новгород 2018 год

Оглавление

Введение. 2

Обзор литературы. 3

История возникновения теории графов. 4

Решение Задачи «о семи мостах Кенигсберга». 5

Основные понятия в теории графов. 6

Определение понятия «граф». 9

Виды графов. 9

Задачи на теорию графов. 11

Материалы и методики. 14

Применение графов. 14

Типы социологических и социально-психологических задач, решаемых с помощью Теории графов. 17

Применение теории графов в химии. 21

Применение теории графов в биологии и медицине. 24

Сети заболеваний человека. 25

Сети ДНК.. 26

Проблема Гамильтонова пути. 28

Результаты применения разработанных методик теории графов. 30

Генетика цвета глаз. 30

Определение цвета глаз с помощью теории графов. 31

Заключение. 32

Списоклитературы.. 33

Отзыв научного руководителя. 36

Введение

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

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

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

Обзор литературы

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

В настоящее время существует крайне обширная литература по теории графов, исследующая как чисто научные проблемы, так и области и методы ее применения. В частности, одной из самых популярных книг по проблемам современной прикладной математики является монография американских ученых М. Гэри и Д. Джонсона "Вычислительные машины и труднорешаемые задачи", посвященная вопросам сложности решения комбинаторных задач, возникающих в дискретной оптимизации, математическом программировании, алгебре, теории чисел, теории автоматов, математической логике, теории множеств, теории графов и т.п. Книга отличается строгим и систематическим изложением теории в приложении содержится более 300 труднорешаемых задач из различных разделов математики, значительная часть которых относится именно к теории графов. Более того, для большинства остальных задач, приведенных в данной фундаментальной монографии, уже успевшей стать классикой, описаны пути сведения их к задачам на графах.

Среди других наиболее известных книг по теории графов можно выделить, например, такие работы, как «Теория графов. Алгоритмический подход" Н. Кристофидеса, «Введение в теорию графов» О. Оре, "Теория графов» Ф. Харари, хотя список литературы по данной теории и ее применению на практике практически неисчерпаем и ежегодно пополняется все новыми и новыми глубокими исследованиями.

История возникновения теории графов

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

13 марта 1736 года Эйлер в письме итальянскому математику и инженеру  Джованни Джакобо Маринони приводит правило, пользуясь которым, легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них. В данном случае ответ был: «нельзя». В письме Карлу Готлибу Элеру от 3 апреля 1736 года Эйлер обосновывает найденное им правило, а позднее на эту тему Эйлер публикует статью в научном журнале Петербургской академии наук «Commentarii Academiae Scientiarum Imperialis Petropolitanae».

     Сам Термин "граф" впервые ввел Сильвестр, Джеймс Джозеф в 1878 году в своей статье в Nature.

Решение Задачи «о семи мостах Кенигсберга»

Семь мостов Кенигсберга - старинная математическая задача, в которой спрашивалось, как можно пройти по всем семи мостам Кёнигсберга, не проходя ни по одному из них дважды. На упрощённой схеме города (графе) мостам соответствуют линии (ребра графа), а частям города — точки соединения линий (вершины графа). В ходе рассуждений Эйлер пришёл к следующим выводам:

·        Число нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа должно быть чётно. Не может существовать граф, который имел бы нечётное число нечётных вершин.

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

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

·        Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком.

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

Основные понятия в теории графов

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

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

Определение 1.Друг другу инцидентны две вершины графа, если они соединены ребром; вершина и ребро графа инцидентны, если вершина является началом или концом ребра.

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

Определение 3. Степенью вершины называется число ребер, которым принадлежит вершина.

Обозначение: p(A)–степень вершины A.

Определение 4. Граф, степени всех k вершин которого одинаковы, называется однородным графом степень к

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

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

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

Определение 8. Путем от А до X называется последовательность ребер, ведущая от A к X, такая, что каждые два соседних ребра имеют общую вершину, и никакое ребро не встречается более одного раза.

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

Определение 10. Простым циклом называется цикл, не проходящий ни через одну из вершин графа более одного раза.

Определение 11. Длиной пути, проложенного на цикле, называется число ребер этого пути.

Определение 12. Две вершины А и В в графе называются связными (несвязными), если в нем существует (не существует) путь, ведущий из А в В

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

Определение 14.Компонентой связности графа (или просто компонентой графа) называется максимальный (по включению) связный подграф графа. Другими словами, это подграф , порождённый множеством вершин, в котором для любой пары вершин в графе существует -цепь и для любой пары вершин , не существует -цепи.

Определение 15.Матрицей смежности графаG с конечным числом вершин n пронумерованных числами от 1 до n) называется квадратная матрица A размера n, в которой значение элемента а_ij равно числу рёбер из i-й вершины графа в j-ю вершину.

Определение 16. Матрицей инцидентности называется одна из форм представления графа, в которой указываются связи между инцидентными элементами графа (ребро(дуга) и вершина). Столбцы матрицы соответствуют ребрам, строки — вершинам. Ненулевое значение в ячейке матрицы указывает связь между вершиной и ребром (их инцидентность).

В случае ориентированного графа каждой дуге <x,y> ставится в соответствующем столбце: «−1» в строке вершины x и «1» в строке вершины y; если связи между вершиной и ребром нет, то в соответствующую ячейку ставится «0».

Определение понятия «граф»

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

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

В дальнейшем вершины графа мы будем обозначать латинскими буквами A , B ,C ,D . Иногда граф в целом будем обозначать одной заглавной буквой.

Виды графов

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

Ориентированный граф(орграф) – граф, ребрам которого присвоено направление

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

Смешанный граф -  это граф, в котором некоторые ребра могут быть ориентированными, а некоторые – неориентированными. Ориентированный и неориентированный графы являются частными случаями смешанного.

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

1)               Графы имеют одинаковое количество вершин и ребер.

2)               Вершины графов имеют одинаковые степени (в них сходятся одинаковое количество ребер)

Взвешенный граф(орграф) -  это граф, некоторым элементам которого присвоены числа. Наиболее часто встречаются графы с помеченными ребрами.

Эйлеров граф – граф, содержащий эйлеров цикл, проходящий через каждое ребро графа ровно по одному разу.

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

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

Гамильтонов граф – граф, содержащий гамильтонов цикл, замкнутый путь, который содержит все вершины (точки) данного графа.

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

Нулевой граф -  граф состоящий из «изолированных» вершин без ребер.

Задачи на теорию графов

Задача 1: задача коммивояжера

Задача коммивояжера - одна из самых известных задач комбинаторной оптимизации, заключающаяся в поиске самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. В условиях задачи указываются критерий выгодности маршрута (кратчайший, самый дешёвый, совокупный критерий и тому подобное) и соответствующие матрицы расстояний, стоимости и тому подобного. Как правило, указывается, что маршрут должен проходить через каждый город только один раз — в таком случае выбор осуществляется среди гамильтоновых циклов. 

Это оптимальный маршрут коммивояжёра через 15 крупнейших городов Германии. Указанный маршрут является самым коротким из всех возможных 43589145600вариантов.

Задача 2: Росчерком пера

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

Многие типы задач на теорию графов можно встретить в ОГЭ и ЕГЭ. Приведем пару примеров, на решение таких задач.

Задача 3:Необходимо составить фрагмент расписания для одного дня занятий с учетом следующих обстоятельств:

·         учитель истории может дать либо первый, либо второй, либо третий уроки, но только один урок:

·         учитель литературы может дать один, либо второй, либо третий урок;

·         математик готов дать либо только первый, либо только второй урок;

·         Преподаватель физкультуры может дать только последний урок.

Сколько можно составить вариантов расписания так, чтобы оно устроило всех учителей? (Обозначения: М – математика, Ф – физкультура, И – история, Л – литература)

Решение:

Согласно условию задачи, первый урок может провести Ии М, второй – И, Л и М, третий – И или Л, и четвертый урок – только Ф.

Построим усеченный граф-дерево.  Ветви, которые отсекаются на этапе построения, указаны красным цветом.

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

Ответ: три варианта.

Задача 4: Для составления цепочек разрешается использовать бусины 5 типов, обозначаемых буквами  А, Б, В, Е, И. Каждая цепочка должна состоять из трех бусин, при этом должны соблюдаться следующие правила:

а) на первом месте стоит одна из букв: А, Е, И,

б) после гласной буквы в цепочке не может снова идти гласная, а после согласной – согласная,

в) последней буквой не может быть А.

Какая из цепочек построена по этим правилам?

1)       АИБ           2) ЕВА           3) БИВ           4) ИБИ

Решение

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

Например, вопрос может звучать так: Сколько существует возможных вариантов из 3 бусин, удовлетворяющих заданному условию?

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

 

 

Материалы и методики

Применение графов

Графы в теории массового обслуживания

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

Графы в математике.

В математике графы применяются для решения логических задач и головоломок. Основной применения графов для решения логических задач служит выявление и последовательное исключение возможностей, заданных в условии. Это выявление логических возможностей часто может быть истолковано с помощью построения и рассмотрения соответствующих графов. Возьмем, к примеру, такую задачу: «Беседуют трое: Белокуров, Чернов и Рыжов. Брюнет сказал Белокурову: «Любопытство, что один из нас русый, другой - брюнет, а третий - рыжий, но никого цвет волос не соответствует фамилии». Какой цвет волос имеет из беседующих?» Решение данной задачи можно изобразить с помощью графа.

Графы в физике.

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

Теория графов в психологии.

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

Теория графов в логистике.

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

Теория графов в химии.

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

Молекулярный граф — связный неориентированный граф, находящийся во взаимно-однозначном соответствии со структурной формулой химического соединения таким образом, что вершинам графа соответствуют атомы молекулы, а рёбрам графа — химические связи между этими атомам.

Типы социологических и социально-психологических задач, решаемых с помощью Теории графов

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

1) Формализация и построение общей структурной модели социального объекта на разных уровнях его сложности. Например, структурная схема организации, социограммы, сравнение систем родства в разных обществах, анализ ролевой структуры групп и т.д. Можно считать, что ролевая структура включает три компонента: лица, позиции (в упрощенном варианте - должности) и задачи, выполняемые в данной позиции. Каждая компонента может быть представлена в виде графа:

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

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

3) Изучение уровней структуры иерархических организаций: количество уровней, количество связей, идущих из одного уровня в другой и от одного лица к другому. На основании этого решаются задачи:

а) количественной оценки веса (статуса) индивида в иерархической организации. Одним из возможных вариантов определения статуса является формула:

где r (р) - статус некоторого лица р, k - величина уровня субординации, определяемая как наименьшее количество шагов от данного лица к своему подчиненному, nk - количество лиц на данном уровне k., например, в организации, представленной след. графом:

вес, а=1·2+2·7+3·4=28; 6=1·3+2·3=9 и т.д.

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

Наиболее простой способ дается формулой: r=Σdxy/Σdqx, т.е. частное от деления суммы всех дистанций каждого до всех других на сумму дистанций данного индивида до всех других.

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

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

Применение теории графов в химии

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

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

В стереохимии орг. в-в наиболее часто используют молекулярные деревья - остовные деревья молекулярных графов, которые содержат только все вершины, соответствующие атомам Составление наборов молекулярных деревьев и установление их изоморфизма, позволяют определять молекулярные структуры и находить полное число изомеров алканов, алкенов и алкинов. Молекулярные графы дают возможность сводить задачи, связанные с кодированием, номенклатурой и структурными особенностями (разветвленность, цикличность и т.п.) молекул различных соединений, к анализу и сопоставлению чисто математических признаков и свойств молекулярных графов и их деревьев, а также соответствующих им матриц. Для выявления количества корреляций между строением молекул и физико-химическими (в т.ч. фармакологическими) свойствами соединений разработано более 20 т. наз. Топологических индексов молекул (Винера, Балабана, Хосойи, Плата, Рандича и др.), которые определяют с помощью матриц и числовых характеристик молекулярных деревьев. Напр., индекс Винера W = (m3 + m)/6, где т-число вершин, отвечающих атомам С, коррелирует с молекулярными объемами и рефракциями, энтальпиями образования, вязкостью, поверхностным натяжением, хроматографическими константами соединений , октановыми числами углеводородов и даже физиол. активностью лекарственных препаратов. Важными параметрами молекулярных графов, используемыми для определения таутомерных форм данного вещества и их реакционной способности, а также при классификации аминокислот, нуклеиновых кислот, углеводов и др. сложных природных соединений, являются средняя и полная (Н)информационная емкости. Анализ молекулярных графов полимеров, вершины которых отвечают мономерным звеньям, а ребра-химическими связям между ними, позволяет объяснить, например, эффекты исключенного объема, приводящие к качествам. изменениям прогнозируемых свойств полимеров. С применением Теории графов и принципов искусственного интеллекта разработано программное обеспечение информационно-поисковых систем в химии, а также автоматизированных систем идентификации молекулярных структур и рационального планирования органического синтеза. Для практической реализации на ЭВМ операций выбора рациональных путей хим. превращений на основе ретросинтетического и синтонного принципов используют многоуровневые разветвленные графы поиска вариантов решений, вершины которых соответствуют молекулярным графам реагентов и продуктов, а дуги изображают превращения.

Для решения многомерных задач анализа и оптимизации химико-технологических систем (ХТС) используют следующие химико-технологические графы: потоковые, информационно-потоковые, сигнальные и графы надежности. Для изучения в хим. физике возмущений в системах, состоящих из большого числа частиц, используют т. наз. диаграммы Фейнмана-графы, вершины которых отвечают элементарным взаимодействиям физических частиц, ребра их путям после столкновений. В частности, эти графы позволяют исследовать механизмы колебательных реакций и определять устойчивость реакционных систем. Материальные потоковые графы отображают изменения расходов в-в ХТС. Тепловые потоковые графы отображают балансы теплоты в ХТС; вершины графов соответствуют аппаратам, в которых изменяются расходы теплоты физических потоков, и, кроме того, источникам и стокам тепловой энергии системы; дуги отвечают физическим и фиктивным (физ.-хим. превращения энергии в аппаратах) тепловым потокам, а веса дуг равны энтальпиям потоков. Материальные и тепловые графы используют для составления программ автоматизированной разработки алгоритмов решения систем уравнений материальных и тепловых балансов сложных ХТС. Информационно-потоковые графы отображают логико-информационную структуру систем уравнений мат. моделей ХТС; применяются для составления оптимальных алгоритмов расчета этих систем. Двудольный информационный граф неориентированный или ориентированный граф, вершины которого отвечают соотв. уравнениям fl -f6 и переменным q1 – V, а ветви отображают их взаимосвязь. Информационный граф – орграф, изображающий порядок решения уравнений; вершины графа отвечают этим уравнениям, источникам и приемникам информации ХТС, а ветви-информац. переменным. Сигнальные графы соответствуют линейным системам уравнений математических моделей химико-технологических процессов и систем. Графы надежности применяют для расчета различных показателей надежности Х.

Применение теории графов в биологии и медицине

В конце двадцатого века на основе теории графов сформировалась новая область статистической физики – теория сложных сетей, ставшая эффективным инструментом исследования сложных систем различной природы, в том числе биологии и медицины. В последние годы приложения теории сложных сетей к проблемам возникновения болезней человека привело к возникновению нового направления в медицине – сетевой медицины (Network Medicine). Цель данной статьи – представить краткий обзор наиболее важных   публикаций этого научного направления, прежде всего связанных с пониманием проблемы взаимосвязи различных заболеваний.

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

Чаще всего болезнь вызванавзаимодействием процессов на молекулярном уровне. Взаимосвязи между этими процессами отображаются в интерактоме– многослойной сетевой структуре, включающей в себя все взаимодействия в живой клетке: от сети взаимодействий белок-белок до регуляторных сетей и сетей метаболических реакций. Несколько лет назад стало известно свойство связанных с болезнями белков взаимодействовать между собой. Это дало основание предположить, что такие белки образуют винтерактомекластер, содержащий все связанные между собой молекулярные субстраты болезни. Этот кластер получил название модуль заболевания.

Сети заболеваний человека

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

В качестве примера можно привести недавние исследования, которые показали, что если у человека одна из аллелей содержит ген FTO, то у этого человека риск ожирения возрастает на 30%, а если этот ген содержится в обеих аллелях, риск ожирения возрастает до 67%. Такая связь между геном FTO и ожирением может служить примером сильной прямой связи между генотипом и фенотипом.  При этом избыточный вес оказывается тесно связанным такими заболеваниями, как сахарный диабет, астма и другими.

Недавно Кристакис и Фаулер изучив данные многолетних медицинских наблюдений различных социальных групп в одном из районов штата Массачусетс (США), обнаружили, что социальные связи различной природы оказывают на возникновение избыточного веса не меньшее влияние, чем генетические факторы. Например, вероятность того, что если друг вашего друга достаточно хорошо знаком с человеком с избыточным весом, он сам наберет избыточный вес, на 20% выше, чем в социальных сетях со случайными связями между людьми. Было показано, что ожирение подобно инфекциям распространяется по социальным сетям.

В настоящее время имеется множество данных, в которых устанавливаются связи между заболеваниями в виде сетей. Например, Rzhetsky et al установили связи между 161 сопутствующими друг другу заболеваниями на основе данных взятых из истории болезней полутора миллиона пациентов по программе Medicare. Hidalgo et al построили сеть фенотипических признаков заболеваний используя данные о сопутствующих друг другу болезнях более 30 миллионов пациентов, показав, симптомы не только по-прежнему являются решающим фактором правильного клинического диагноза и успешного лечения, но и важнейшим ресурсом для теоретического анализа.

Сети ДНК

В статье «APPLICATIONOFGRAPHTHEORYTOBIOLOGICALPROBLEMS” (NAFI SEHJAFARZADEHa AND ALII RANMANESHa) предложен метод использования задачи «Гамильтонов путь» и найденных к настоящему времени подходов к ее решению для изучения ДНК.

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

Чтобы начать теоретическую фазу применения теории графов, нужен ориентированный граф, который построен из некоторых k-длинных олигонуклеотидов. Фрагментная сборка – это восстановление строки с использованием имеющегося подмножества ее строк. В этом методе данный фрагмент ДНК (или, скорее, много его идентичных копий) разбит на несколько меньших фрагментов. Цель состоит в том, чтобы восстановить исходную строку ДНК на основе ее фрагментов. Поэтому мы имеем следующую задачу:

Для данного мультимножества фрагментов, построить наилучшую строку, содержащую каждую строку в этом мультимножестве.

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

Граф перекрытий мультимножества содержит узел (то есть вершину) для каждой строки в нем. Решение этой задачи приводит к нахождению гамильтонова пути в полученном графе. Отметим, что это пример задачи путешествующего коммивояжера, которая в своем общем виде NP-полна. Даже задача определения существования гамильтонова пути в графе является NP-полной задачей, которая не имеет эффективных алгоритмов для ее решения. Но если мы можем рассмотреть данные  фрагменты как ребра графа перекрытия, это позволяет найти Эйлеров путь и, как мы знаем, это проблема не является NP-полной, и существуют некоторые эффективные алгоритмы для ее решения. Некоторые графы перекрытия были предложены для восстановления последовательностей ДНК.

Проблема Гамильтонова пути

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

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

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

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

Гамильтоновы путь, цикл и граф названы в честь ирландского математика У. Гамильтона, который впервые определил эти классы, исследовав задачу «кругосветного путешествия» по додекаэдру. В этой задаче вершины додекаэдра символизировали известные города, такие как Брюссель, Амстердам, Эдинбург, Пекин, Прага, Дели, Франкфурт и др., а рёбра— соединяющие их дороги. Путешествующий должен пройти «вокруг света», найдя путь, который проходит через все вершины ровно один раз. Чтобы сделать задачу более интересной, порядок прохождения городов устанавливался заранее. А чтобы было легче запомнить, какие города уже соединены, в каждую вершину додекаэдра был вбит гвоздь, и проложенный путь отмечался небольшой верёвкой, которая могла обматываться вокруг гвоздя. Однако такая конструкция оказалась слишком громоздкой, и Гамильтон предложил новый вариант игры, заменив додекаэдр плоским графом, изоморфным графу, построенному на рёбрах додекаэдра.

Результаты применения разработанных методик теории графов

Генетика цвета глаз

Цвет глаз —характеристика, определяемая пигментацией радужной оболочки. Традиционно полагается, что цвет глаз определяется наследственностью. За светлые глаза отвечает мутация (как официально считается) гена OCA2. За синий или зелёный цвет отвечает ген EYCL1 хромосомы 19; за коричневый — EYCL2; за коричневый или синий — EYCL3 хромосомы 15. Кроме того, с цветом глаз связаны гены OCA2, SLC24A4, TYR^. Согласно классической генетике, гены, дающие тёмные глаза, — доминантные, а светлые — рецессивные. Однако в действительности генетика цвета глаз очень сложна, поэтому их комбинации у родителей и детей могут быть крайне разнообразны.

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

Определение цвета глаз с помощью теории графов

Результаты недавних исследований британских ученых-генетиков привели к выводу, что существуют участки по крайней мере в шести генах, по которым можно предсказать цвет глаз. Как заявили по окончании тестов авторы работы, из восьми изученных генов шесть — HERC2, OCA2, SLC24A4, SLC45A2, TYR, IRF4 — вносят в предсказание цвета радужной оболочки максимальный вклад. На основе строения вариабельных участков этих генов карий цвет глаз можно было предсказать с вероятностью 93%, голубой — в 91%. Промежуточный цвет глаз определялся с меньшей вероятностью — в 73%.

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

Я составил родословную своей семьи по цвету глаз, посредством использования орграфа «дерево» (приложение 1). В ходе исследования была использована классификация цветов глаза В.В. Бунака, как наиболее известная в России (приложение 2.

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

Заключение

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

Глубокая идея, лежащая в основе теории, состоит в том, что мощный аппарат теории графов существенно помогает в решении многих практических задач. Теория графов родилась при решении головоломок и игр (задача о Кёнигсберских мостах) и стала мощным средством исследования и решения многих задач, возникающих при решении больших, сложных систем. Сразу после возникновения теории графов стало ясно, что она имеет не только огромную теоретическую ценность, но также и массу практических приложений. Теория графов используется не только в математике, но и в информатике, химии, экономике (для учета затрат), логистике, схемотехнике, в коммуникационных и транспортных системах (в частности, для маршрутизации данных в Интернете). Графы представляют собой наиболее абстрактную структуру, с которой приходится сталкиваться в теории ЭВМ (computerscience). Графы используются для описания алгоритмов автоматического проектирования, в диаграммах машины конечных состояний, при решении задач маршрутизации потоков и т. д.

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

Списоклитературы

Дистель Р. Теория графов Пер. с англ. - Новосибирск: Издательство института математики, 2002. - 336 с. ISBN 5-86134-101-X.

Берж К. Теория графов и её приложения. М.: ИЛ, 1962. 320c.

Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. М.: Наука, 1990. 384с. (Изд.2, испр. М.: УРСС, 2009. 392 с.)

Зыков А. А. Основы теории графов. — М.: «Вузовская книга», 2004. — С. 664. — ISBN 5-9502-0057-8.(М.: Наука, 1987. 383c.)

Химические приложения топологии и теории графов. Под ред. Р. Кинга. Пер. с англ. М.: Мир, 1987.

Кирсанов М. Н. Графы в Maple. М.: Физматлит, 2007. 168 c.

Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978. 429c.

Кормен Т. Х. и др. Часть VI. Алгоритмы для работы с графами// Алгоритмы: построение и анализ = Introductionto Algorithms.— 2-е изд.—М.: Вильямс, 2006. — С. 1296. — ISBN 0-07-013151-1.

Оре О. Теория графов. — 2-е изд. — М.: Наука, 1980. — С. 336.

Свами М., Тхуласираман К. Графы, сети и алгоритмы. М: Мир, 1984. 455с.

Татт У. Теория графов. Пер. с англ. М.: Мир, 1988. 424 с.

Уилсон Р. Введение в теорию графов. Пер с англ. М.: Мир, 1977. 208с.

Харари Ф. Теория графов. — М.: Мир, 1973. (Изд. 3, М.: КомКнига, 2006. — 296 с.)

http://chem.ubbcluj.ro/~studiachemia/issues/chemia2016_1/01Jafarzadeh_Iranmanesh_9_16.pdf

Приложение 1

 

1)    Качкин Николай Никифорович – голубые

2)    Качкина Наталья Михайловна – серо-зеленые

3)    Карасева Анна Матвеевна – серые

4)    Галай Григорий Алексеевич – серые

5)    Тарасова Мария Андреевна – карие

6)    Папа неизвестен

7)    Аралкин Алексей Максимович – карие

8)    Аралкина Мария Алексеевна - голубые

9)    Галай Нина Николаевна - зеленые

10)                       Галай Юрий Григорьевич – серые с голубизной

11)                       Тарасов Валерий Алексеевич - синий

12)                       Тарасова Татьяна Алексеевна – серо-зеленый

13)                       Галай Олег Юрьевич - золотисто-зеленые

14)                       Галай Жанна Валерьевна – синие

15)                       Галай Роман Олегович – серо-зеленый

16)                       Галай Марк Олегович – серо-синие

17)                       Галай Тимур Олегович –серо-зеленые

Приложение 2

Шкала Бунака

·        Тип 1. Тёмный.

·                   Вариант 1. Чёрный.

·                   Вариант 2. Тёмно-карий. Окраска равномерная.

·                   Вариант 3. Светло-карий. Окраска неравномерная.

·                   Вариант 4. Жёлтый. Очень редкий вариант.

·        Тип 2. Переходный, смешанный.

·                   Вариант 5. Буро-жёлто-зелёный.

·                   Вариант 6. Зелёный.

·                   Вариант 7. Серо-зелёный.

·                   Вариант 8. Серый или голубой, вокруг зрачка — буро-жёлтое обрамление.

·        Тип 3. Светлый.

·                   Вариант 9. Серый. Может быть разных оттенков.

·                   Вариант 10. Серо-голубой. Окраска неравномерная.

·                   Вариант 11. Голубой.

·                   Вариант 12. Синий. Встречается редко.

Отзыв научного руководителя

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

Содержание работы соответствует заявленной теме.

     Текст работы изложен на 31-ом листе печатного текста, что представляется вполне достаточным для ученика 9 класса.

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

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

Коган Г.П.