Файл: Реферат По теме Применение графов в программировании Студент группы ит21 Кульпина А. В.rtf
Добавлен: 06.12.2023
Просмотров: 27
Скачиваний: 3
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Министерство Образования Саратовской Области
Государственное Автономное Профессиональное
Образовательное Учреждение Саратовской Области
«Вольский Технологический колледж»
Реферат
По теме: Применение графов в программировании
Выполнил:
Студент группы ИТ-21
Кульпина А.В.
Проверил преподаватель:
Бабочкина Т.А.
Г. Вольск , 2022
Содержание:
-
Введение -
Способы представления графов в компьютере
2.1. Требования к представлению графов
2.2. Матрица смежности -
Обзор задач теории графов
3.1 Элементы графов -
Представление графов в ЭВМ
4.1 Требования к представлению графов -
Заключение -
Список использованной литературы
-
Введение
Начало теории графов как математической дисциплины было положено Эйлером в его знаменитом рассуждении о Кенигсбергских мостах. Однако эта статья Эйлера 1736 года была единственной в течение почти ста лет. Интерес к проблемам теории графов возродился около середины прошлого столетия и был сосредоточен главным образом в Англии. Имелось много причин для такого оживления изучения графов. Естественные науки оказали свое влияние на это благодаря исследованиям электрических цепей, моделей кристаллов и структур молекул. Развитие формальной логики привело к изучению бинарных отношений в форме графов. Большое число популярных головоломок подавалось формулировкам непосредственно в терминах графов, и это приводило к пониманию, что многие задачи такого рода содержат некоторое математическое ядро, важность которого выходит за рамки конкретного вопроса. Наиболее знаменитая среди этих задач-проблема четырех красок, впервые поставленная перед математиками Де Морганом около 1850 года. Никакая проблема не вызывала столь многочисленных и остроумных работ в области теории графов.
Настоящее столетие было свидетелем неуклонного развития теории графов, которая за последние десять - двадцать лет вступила в новый период интенсивных разработок. В этом процессе явно заметно влияние запросов новых областей: теории игр и программирования, теории передачи сообщений, электрических сетей и контактных цепей, а также проблем психологии и биологии.
Вследствие этого развития предмет теории графов является уже обширным, что все его основные направления невозможно изложить в одном томе. В настоящем первом томе предлагаемого двухтомного труда сделан акцепт на основные понятия и на результаты, вызывающие особый систематический интерес.
2. Способы представления графов в компьютере
Конструирование структур данных для представления в программе объектов математической модели – это основа искусства практического программирования. Далее приводится четыре различных базовых представления графов. Выбор наилучшего представления определяется требованиями конкретной задачи. Более того, при решении конкретных задач используются, как правило, некоторые комбинации или модификации указанных представлений, общее число которых необозримо. Но все они так или иначе основаны на тех базовых идеях, которые описаны в этом разделе.
2.1 Требования к представлению графов
Известны различные способы представления графов в памяти компьютера, которые различаются объемом занимаемой памяти и скоростью выполнения операций над графами. Представление выбирается, исходя из потребностей конкретной задачи. Далее приведены четыре наиболее часто используемых представления с указанием характеристики n(p,q) – объема памяти для каждого представления. Здесь p – число вершин, а q – число ребер.
2.2 Матрица смежности
Представление графа с помощью квадратной булевой матрицы M, отражающей смежность вершин, называется матрицей смежности, где для матрицы смежности n(p,q) = O(p2).
Замечание:
Матрица смежности неориентированного графа симметрична относительно главной диагонали, поэтому достаточно хранить только верхнюю (или нижнюю) треугольную матрицу.
3. Обзор задач теории графов
Развитие теории графов в основном обязано большому числу всевозможных приложений. По-видимому, из всех математических объектов графы занимают одно из первых мест в качестве формальных моделей реальных систем.
Графы нашли применение практически во всех отраслях научных знаний: физике, биологии, химии, математике, истории, лингвистике, социальных науках, технике и т.п. Наибольшей популярностью теоретико-графовые модели используются при исследовании коммуникационных сетей, систем информатики, химических и генетических структур, электрических цепей и других систем сетевой структуры.
Далее перечислим некоторые типовые задачи теории графов и их приложения:
- Задача о кратчайшей цепи
· замена оборудования
· составление расписания движения транспортных средств
· размещение пунктов скорой помощи
· размещение телефонных станций
- Задача о максимальном потоке
· анализ пропускной способности коммуникационной сети
· организация движения в динамической сети
· оптимальный подбор интенсивностей выполнения работ
· синтез двухполюсной сети с заданной структурной надежностью
· задача о распределении работ
- Задача об упаковках и покрытиях
· оптимизация структуры ПЗУ
· размещение диспетчерских пунктов городской транспортной сети
- Раскраска в графах
· распределение памяти в ЭВМ
· проектирование сетей телевизионного вещания
- Связность графов и сетей
· проектирование кратчайшей коммуникационной сети
· синтез структурно-надежной сети циркуляционной связи
· анализ надежности стохастических сетей связи
- Изоморфизм графов и сетей
· структурный синтез линейных избирательных цепей
· автоматизация контроля при проектировании БИС
- Изоморфное вхождение и пересечение графов
· локализация неисправности с помощью алгоритмов поиска МИПГ
· покрытие схемы заданным набором типовых подсхем
- Автоморфизм графов
· конструктивное перечисление структурных изомеров для производных органических соединений
· синтез тестов цифровых устройств
3. Виды графов и операции над ними
3.1 Элементы графов
Для рассмотрения видов граф и операций над ними необходимо познакомиться с такими понятиями как подграфы, маршрут, цепь, цикл.
Граф G'(V', Е') называется подграфом графа G(V, Е) (обозначается G' Ì G), если V' Ì V и/или Е' Ì Е.
Если V' = V, то G ' называется остовным подграфом G.
Если V' Ì V & Е' Ì Е & (V' ¹ V Ú Е' ¹ Е), то граф G ' называется собственным подграфом графа G.
Подграф G'(V' , Е') называется правильным подграфом графа G(V,Е), если G ' содержит все возможные ребра G:
" и,v Î V' (и, v) Î Е Þ (и, v) Î Е'.
Правильный подграф G '(V ' , Е') графа G (V, Е) определяется подмножеством вер шин V '.
Маршрутом в графе называется чередующаяся последовательность вершин и ребер в которой любые два соседних элемента инцидентны.
v0, e1, v1, e2, v2,…,ek, vk,
Это определение подходит также для псевдо-, мульти- и орграфов. Для «обычного» графа достаточно указать только последовательность вершин или только последовательность ребер.
Если v0 = vk, то маршрут замкнут, иначе открыт. Если все ребра различны, то маршрут называется цепью. Если все вершины (а значит, и ребра) различны, то маршрут называется простой цепью. В цепи v0, e1, v1, e2, v2,…,ek, vk,
вершины v0 и vk, называются концами цепи. Говорят, что цепь с концами и и v соединяет вершины и и v. Цепь, соединяющая вершины и и v, обозначается (и, v). Очевидно, что если есть цепь, соединяющая вершины и и v, то есть и простая цепь, соединяющая эти вершины.
Замкнутая цепь называется циклом; замкнутая простая цепь называется простым циклом. Число циклов в графе G обозначается z(G). Граф без циклов называется ациклическим.
Элементы графа – любое чередование вершин и рёбер графа, в котором каждому ребру предшествует смежная ей вершина, называющаяся контуром графа.
A, C, A, D – маршрут, но не цепь;
A, C, E, B, C, D – цепь, но не простая цепь;
A, D, C, B, E, - простая цепь;
A, C, E, B, C, D, A – цикл, но не простой цикл;
A, C, D – простой цикл;
Цепь в ориентированном графе называется путём, а цикл – контуром.
4. Представление графов в ЭВМ
Следует еще раз подчеркнуть, что конструирование структур данных для представления в программе объектов математической модели — это основа искусства практического программирования. Используется четыре различных базовых представления графов. Выбор наилучшего представления определяется требованиями конкретной задачи. Более того, при решении конкретных задач используются, как правило, некоторые комбинации или модификации указанных представлений, общее число которых необозримо. Но все они, так или иначе, основаны на тех базовых идеях, которые описаны в этом разделе.
4.1 Требования к представлению графов
Известны различные способы представления графов в памяти компьютера, которые различаются объемом занимаемой памяти и скоростью выполнения операций над графами. Представление выбирается, исходя из потребностей конкретной задачи. Далее приведены четыре наиболее часто используемых представления с указанием характеристики п(р, q) — объема памяти для каждого представления. Здесь р - число вершин, а q - число ребер. Указанные представления пригодны для графов и орграфов, а после некоторой модификации также и для псевдографов, мультиграфов и гиперграфов.
1. Матрица смежности. Представление граф с помощью квадратной булевской матрицы, отражающей смежность вершин, называется матрицей смежности,
M : array [1..p, 1..p] of 0..1,
M.. [i, j] = 1, если вершина vi смежна с вершиной vj
0, если вершины не vi и vj смежны.
Для матрицы смежности п(р, q) = O(p2).
2. Матрица инциденций. Представление графа с помощью матрицы H : array [1..p, 1..q] of 0..1 (для орграфов H : array [1..p, 1..q] of -1..1), отражающей инцидентность вершин и рёбер, называется матрицей инциденций, где для неориентированного графа
H.. [i, j] = 1, если вершина vi инцидентна ребру ej,
0, в противном случае.
а.. для ориентированного графа
1, если вершина vi инцидентна ребру ej и является его концом,
H [i, j] = 0, если вершина vi и ребро ej не инцидентны,
-1, если вершина vi инцидентна ребру ej и является его началом
3. Списки смежности. Представление графа с помощью списочной структуры, отражающей смежность вершин и состоящей из массива указателей Г : array [1..р] оf N на списки смежных вершин (элемент списка представлен структурой N : record v: 1..р; п : N endrecord), называется списком смежности. В случае представления неориентированных графов списками смежности п(р, q) = О(р + 2q), а в случае ориентированных графов п(р, q) = О(р + q).
4. Массив дуг. Представление графа с помощью массива структур Е : array [1..р] of record b,e : 1..p endrecord, отражающего список пар смежных вершин, называется мас сивом ребер (или, для орграфов, массивом дуг). Для массива ребер (или дуг) п(р, q) = О( 2q).
5. Обход графа — это некоторое систематическое перечисление его вершин (и/или ребер). Наибольший интерес представляют обходы, использующие локальную информацию (списки смежности). Среди всех обходов наиболее известны поиск в ширину и в глубину. Алгоритмы поиска в ширину и в глубину лежат в основе многих конкретных алгоритмов на графах.
ТЕОРЕМА Если граф G связен (и конечен), то поиск в ширину и поиск в глубину обойдут все вершины по одному разу.
Доказательство
1. Единственность обхода вершины. Обходятся только вершины, попавшие в Т. В Т попадают только неотмеченные вершины. При попадании в Т вершина отмечается. Следовательно, любая вершина будет обойдена не более одного раза.
Завершаемость алгоритма. Всего в Т может попасть не более р вершин. На каждом шаге одна вершина удаляется из Т. Следовательно, алгоритм завершит работу не более чем через р шагов.
Обход всех вершин. От противного. Пусть алгоритм закончил работу, и вер шина w не обойдена. Значит, w не попала в Т. Следовательно, она не былаотмечена. Отсюда следует, что все вершины, смежные с w, не были обойденыи отмечены. Аналогично, любые вершины, смежные с неотмеченными, самине отмечены (после завершения алгоритма). Но G связен, значит, существуетпуть (v,w). Следовательно, вершина v не отмечена. Но она была отмечена напервом шаге.