Смешанные графы

Содержание Введение 1 Смешенный граф и формула его перечисления. 2 Полный граф и формула его перечисления 7 Кратчайшие пути 10 Заключение 14 Библиографический список 15 Введение В последние годы особую важность приобрели те разделы математики, которые имеют отношение к развитию цифровых устройств, цифровой связи и цифровых вычислительных машин. Базой для преподавания этих дисциплин наряду с классическими методами анализа непрерывных физических моделей стали алгебраические, логические и комбинаторные методы исследования различных моделей дискретной математики.

Значительно возросла популярность теории графов – ветви дискретной математики. Графы встречаются во многих областях под разными названиями: "структуры" в гражданском строительстве, "сети" – в электронике, "социограммы" – в социологии и экономике, "молекулярные структуры" – в химии, "дорожные карты", электрические или газовые распределительные сети и т. д. [8] Родившись при решении головоломок и игр, таких, например, как задача о кенигсбергских мостах и игра Гамильтона, теория графов стала мощным средством исследования и решения многих задач, возникающих при изучении больших и сложных систем.

Для специалистов по вычислительной технике, информационным системам и системам цифровой связи теория графов – это удобный язык выражения понятий из этой области; многие результаты теории графов имеют непосредственную связь с задачами, с которыми им приходится сталкиваться. [7] В данной работе я рассмотрю понятие смешанного графа.

Смешанный граф G — это граф, в котором некоторые рёбра могут быть ориентированными, а некоторые — неориентированными. Записывается упорядоченной тройкой G := (V, E, A), где V - это множество вершин или узлов, E - это множество пар (неупорядоченных) различных вершин, называемых рёбрами и A - это множество (упорядоченных) пар различных вершин, называемых дугами или ориентированными рёбрами.

Понятно, что ориентированный и неориентированный графы являются частными случаями смешанного.

Смешенный граф и формула его перечисления

2 16 смешанных графов третьего порядка. Пусть mpqr — число смешанных графов с р вершинами, q ориентированными ... Таким образом, Z ( ; Sk, tk) является цикловым индексом редуцированной... Подставляя перечисляющие ряды для фигур: и, приходим к выражению (7), ... Заметим, что каждый из этих многочленов легко получается из mp(х, у), ...

Полный граф и формула его перечисления

Полный граф и формула его перечисления. 4 следует, что при р = 3 формула имеет вид с3(х, у) = 2х3 + Зх2у + ху2... Следствие. Перед началом первой итерации алгоритма вершина s имеет постоянную мет... Положить l(v):=∞ для всех v € VG, v≠s, и считать э...

Заключение

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

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

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

Библиографический список

– Мн.: Мир, 1976 . – М.: Наука,1990. 4. – 424с. Интернет источники: 7.