Теория графов и ее применение к сетевым измерениям.

Оглавление
1.Введение. Теория графов как раздел дискретной математики
2. Основные определения теории графов
3. Способы матричного представления графов, их сравнение, достоинства и недостатки.
4. Операции над матрицами и графами
5. Маршруты, цепи и циклы графов.
6. Ориентированные графы
7. Эйлеровы циклы
8. Гамильтоновы циклы
9. Двудольные графы
10. Деревья
11. Включение сетевых подходов в общую структуру анализа данных
12. Сетевые подходы и регрессионный, факторный, кластерный анализ
13. Социальные сети и марковские процессы
14. Сетевой подход в теории игр
Заключение
Список литературы

Количество требований на обслуживание и временные интервалы между их поступлением носят случайный характер, их нельзя предсказать с однозначной определенностью. Однако в своей совокупности множество таких требований подчиняется определенным статистическим закономерностям, количественное изучение которых и является предметом теории массового обслуживания. Экономическая кибернетика анализирует экономические явления и процессы в качестве очень сложных систем с точки зрения законов и механизмов управления и движения информации в них. Наибольшее распространение в экономическом анализе получили методы моделирования и системного анализа. В ряде случаев приходится находить решение экстремальных задач при неполном знании механизма рассматриваемого явления. Такое решение отыскивается экспериментально. В последние годы в экономической науке усилился интерес к формализации методов эмпирического поиска оптимальных условий протекания процесса, использующих человеческий опыт и интуицию. 13. Социальные сети и марковские процессыМарковские случайные процессы названы по имени выдающегося русского математика А.А.Маркова (1856-1922), впервые начавшего изучение вероятностной связи случайных величин и создавшего теорию, которую можно назвать "динамикой вероятностей". Случайный процесс Х (t) называется марковским, если для любых двух моментов времени t0 и t1 (t0 < t1) условное распределение вероятностей X (t1) при условии, что заданы все значения Х (t) при t < t0, зависит только от X (t0) (в силу этого Марковские случайные процессы иногда называют процессами без последействия). Марковские процессы являются естественным обобщением детерминированных процессов. В детерминированных процессах состояние системы в момент времени t0 однозначно определяет ход процесса в будущем; в Марковских процессах состояние системы в момент времени t0 однозначно определяет распределение вероятностей хода процесса при t > t0, причём никакие сведения о ходе процесса до момента времени t0 не изменяют это распределение.Таким образом, процесс, протекающий в экономической системе, называется Марковским, если в любой момент времени вероятность любого состояния системы в будущем зависит только от состояния системы в текущий момент и не зависит от того, каким образом система пришла в это состояние. Марковские модели нашли широкое применение в задачах управления. Они составляют основу современного арсенала вероятностных методов применительно к описанию состояний управляемого объекта и процесса перехода из одного состояния в другое с течение времени с приемлемой степени точности и достоверностью.Основные свойства Марковских процессов можно представить следующим образом:- исходная задача управления стохастической системой погружается в семейство динамических оптимизационных задач, каждый этап управления имеет свою задачу принятия оптимального решения;- множество решений оптимизационных задач описывается функциональным уравнением динамического программирования;- оптимальные решения находятся с помощью обратного хода алгоритма, представляющего собой упорядоченную процедуру обработки данных как результатов решения последовательности функциональных уравнений;- оптимальное управление обладает тем свойством, что каковы бы ни были начальное состояние и решение, принимаемое в этом состоянии, последующие решения образуют оптимальную политику для того этапа, который возникает после первых решений и следовательно переходов.С учетом влиятельности участников сети – ее агентов вся сеть разделана на группы, сообщества и спутники. Сообществом называют множество агентов, которые не подвергаются влиянию агентов внеего. Группа - сообщество агентов, в котором любые два агента влияют друг на друга прямым или косвенным образом. Спутник – агент, подвергшийся влиянию агентов тех или иных групп, однако не оказывающий влияния ни на одну из них и их «внутренних агентов». Интерес безусловно представляет структура результирующего влияния. При наличии в сети агентов с ненулевыми довериями, что соответствует сети с неавтономными агентами, из теории марковских процессов следуют важные для приложений социальных сетей выводы, а именно:существуетматрицарезультирующихвлияний;мненияагентовстабилизируются;результирующее влияние спутника на любого агента равно нулю;итоговые мнения агентов группы также стабилизируются и группа в итоге имеет общее мнение, которое можно считать мнением группы. Последнее утверждение соответствует наблюдениям социальных психологов о том, что в группы в конце концов приходят к консенсусу. ГруппыСпутникиРис. 1. Структура результирующих влияний в социальной сети14. Сетевой подход в теории игрЭкономико-математические модели могут строиться не только в виде формул (аналитическое представление модели), но и в виде числовых примеров (численное представление), в виде таблиц (матричное) и в виде графов (сетевое представление).Соответственно по этому принципу различают модели:АналитическиеМатричныеСетевыеВ анализе хозяйственной деятельности используется метод сетевого планирования. Он базируется на применении сетевых графиков. Последние выражаются в виде определенной цепи работ и событий, связанных технологической последовательностью. Под работой здесь понимается процесс, который предшествует возникновению определенного события. Работа включает как технологические процессы, так и время ожидания, сопряженное с перерывами в этих процессах. Под событием понимают результат работы, без которого не могут быть начаты другие работы. В сетевых графиках события обозначаются кружками, где внутри пишется номер. Стрелки, помещающиеся между кружками, выражают намеченную последовательность выполнения работ. Числа, указанные возле стрелок, характеризуют намеченную длительность выполнения работ. С помощью сетевых графиков достигается либо оптимизация времени выполнения, либо оптимизация величины себестоимости осуществляемых работ.Сетевая модель определяет с любой требуемой степенью детализации состав работ комплекса и порядок выполнения их во времени.Отличительной особенностью сетевой модели в сравнении с другими формами представления планов является четкое определение всех временных взаимосвязей операций.Сетевые модели используются не только как средство решения разнообразных задач планирования и прогнозирования. Сетевые модели также служат для построения специального класса системы организационного управления, получивших название систем сетевого планирования и управления.Среди различных методом систем сетевого планирования и управления наиболее распространены: метод критического пути — анализ состояния процесса в каждый заданный момент времени и определение последовательности работ с целью избежания задержки времени выполнения плана к намеченному сроку и метод оценки пересмотра программ.ЗаключениеВ последние годы особую важность приобрели те разделы математики, которые имеют отношение к развитию цифровых устройств, цифровой связи и цифровых вычислительных машин. Базой для преподавания этих дисциплин наряду с классическими методами анализа непрерывных физических моделей стали алгебраические, логические и комбинаторные методы исследования различных моделей дискретной математики.Родившись при решении головоломок и игр, таких, например, как задача о кенигсбергских мостах и игра Гамильтона, теория графов стала мощным средством исследования и решения многих задач, возникающих при изучении больших и сложных систем. Для специалистов по вычислительной технике, информационным системам и системам цифровой связи теория графов – это удобный язык выражения понятий из этой области; многие результаты теории графов имеют непосредственную связь с задачами, с которыми им приходится сталкиваться.Список литературы1. Лекции по теории графов / Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. - М.: Наука. Гл. ред. физ.-мат. лит., 2010. - 384 с.2. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика: Пер. с англ./ Предисл. В.Б.Алексеева. - М.: Мир, 2005. - 476 с.3. Майника Э. Алгоритмы оптимизации на сетях и графах: Пер. с англ. - М. Мир, 2011. - 323 с.4. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. - 5-е изд. - М.: Энергоатомиздат, 2008. - 480 с.5. Гэри М., Джонсон Д. Вычислительные машины и трудноразрешимые задачи. - М.: Мир, 2002. - 416 с.6. Кнут Д. Искусство программирования для ЭВМ.т.3. Сортировка и поиск. - М.: Мир, 2008. - 846 с.7. П.Холл. Вычислительные структуры. Введение в нечисленное программирование: Пер. с англ. - М.: Мир, 2008. - 214 с.8. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. - М.: Мир, 2009. - 536 с.9. Кристофидес Н. Теория графов. Алгоритмический подход. – М.: Мир, 2008. - 432 с.10. Берж К. Теория графов и её применения. – М.: ИЛ, 2002. – 319 с.11. Зыков А.А. Основы теории графов. – М.: Наука, 2007. – 381 с.12. Яблонский С.В. Введение в дискретную математику. – М.: Наука, 2006. – 384 с.13. Оре О. Теория графов. – М.: Наука, 2010. – 336 с.14. Свами М., Тхуласираман К. Графы, сети и алгоритмы. – М.: Мир, 2004. – 454 с.15. Уилсон Р. Введение в теорию графов. – М.: Мир, 2007. – 207 с.16. Харари Ф. Теория графов. – М.: Мир, 2003. – 300 с.