Пример готовой курсовой работы по предмету: Программирование
Содержание
Количество ребер графа, с которыми связана вершина, называется
степенью вершины и обозначается как d(v).
Две вершины графа называются
смежными, если существует соединяющее их ребро {v,u} . В этом случае
вершины v и u называют инцидентными этому ребру, а ребро — инцидентным
этим вершинам. Два различных ребра графа называются смежными, если они
имеют хотя бы одну общую вершину.
а) б)
в) г)
Рисунок 1.1 – Пример изображения графов (а – ориентированный; б,г –
неориентированный; в — смешанный)
Маршрут из v 0 в vm. – это последовательность вершин v 0,v 1,…,vm , где v 0
называют начальной вершиной, а vm конечной вершиной маршрута. Длина
маршрута — это количество число ребер в нем. Цепь – это маршрут, в котором
все его ребра различны, и простая цепью, если различны все вершины
v 0,v 1,…,vm. Замкнутая простая цепь, которая содержит по крайней мере одно
ребро, называется циклом.
а) б) в)
Рисунок 1.2 – Исходный граф (а) и его подграфы (б,в)
Путем в графе G – это последовательность ребер e 0,e 1,…,en, где
e 0,e 1,…,en E(G), в котором каждые два соседних ребра имеют общую вершину
и никакое ребро не встречается более одного раза. Путь называется простым,
если он не проходит ни через одну из вершин графа более одного раза. Граф G
называется связным, если для любых двух его вершин v и u существует простая
цепь из v в u.
Граф называется нагруженным или взвешенным, если его вершинам или
ребрам ставится в соответствие некоторая дополнительная информация или вес
(вес вершины или ребра).
Таким образом, граф G(V, E, W) нагруженный если
каждой дуге xk= поставлено в соответствие неотрицательное число
wk=w(vi, vj), называемое весом дуги. Нагруженный граф задается матрицей
весов (см. рис. 1.3).
Длиной пути в нагруженном графе называется сумма весов
всех ребер, в него входящих. Путь из вершины vi в vj называется минимальным
(максимальным), если его длина минимальна(максимальна) среди всех путей из
Выдержка из текста
В настоящее время теория графов имеет многочисленное применение в
различных практических задачах, где необходимо установить соответствия
между объектами. Например, при решении транспортных задач или задач о
потоках в сетях, нефтепроводах, при проектировании и разработке
программного обеспечения, баз данных, в теории игр, теории передачи
сообщений, теории конечных автоматов, электронике или электротехнике.
Теория графов имеет большую привлекательность для специалистов в области
проектирования для построения эффективных алгоритмов и анализа их
сложности, широко применяется в биологии, химии, экономике, социологии и
медицине. В последние время разделы математики, которые имеют отношение к
развитию цифровых устройств, цифровой связи и цифровых вычислительных
машин, приобрели особую важность. Использование математического аппарата
теории графов оказало существенное влияние на разработку, конструирование и
проектирования цифровых схем.
Данная курсовая работа посвящена разработке программного обеспечения
для решения задачи нахождения максимального потока в транспортной сети.
Изучение сетевых моделей началось еще в 40-х годах в связи с транспортными
задачами, где необходимо при определенных поставщиках и потребителях
минимизировать суммарные расходы по доставке товаров. Однако методы,
развитые при анализе такого рода задач, применимы и к другим сетевым
проблемам. К таким задачам можно отнести задачи об информационных
потоках в сетях или задачи о дорожно-транспортных потоках. Целый ряд
прикладных комбинаторных задач, не связанных с реально существующими
сетями, допускает представление задачи в терминах теории графов и
математическое их решение средствами графовых алгоритмов сетевых моделей.
На практике часто возникает задача максимизации потока некоего продукта
между двумя заданными узлами сети при условии, что поток вдоль каждой дуги
ограничен. Очевидный пример – поток городского транспорт
Список использованной литературы
1. Васильев А. Н. Самоучитель Java с примерами и программами. — СПб.:
Наука и Техника, 2011. – 352 с.: ил.
2. Кристофидес Н. Теория графов. Алгоритмический подход. — М.: Мир,
1978.-429с.
3. Лафоре П. Структуры данных и алгоритмы Java. – СПб.: «Питер», 2011.
– 704с.
4. МакГрат М. Программирование на Java для начинающих –
М.:Издательство «Э», 2016. – 192с.
5. Свами М., Тхулалираман К. Графы, сети и алгоритмы. — М: Мир,
1984.-455с.
6. Уилсон Р. Введение в теорию графов. Пер с англ. — М.: Мир, 1977.-
208с.
7. Харари Ф. Теория графов. — М.: Мир, 1973.-296с.
8. Эккель Б. Философия Java. – СПб.: «Питер», 2015. – 1168с.
