Типовой расчет по графам — это использование теории графов при практическом решении типовых задач.
Общие сведения о графах
Графы являются математическими объектами, которые способны оказать помощь при решении очень многих, внешне отличающихся друг от друга, задач. В математике имеется целый подраздел, именуемый теорией графов, изучающий графы, их свойства и методики использования. Существенное расширение области применения теории графов, в том числе в сфере информатики, информационных технологий и компьютерной сфере, связано с тем обстоятельством, что кроме всего прочего, граф ещё может считаться набором структурированных данных. То есть, в компьютерной области и информатике граф выступает как набор нелинейных структурированных данных. Линейной структурой данных считается структура, у которой входящие в её состав элементы связаны отношениями, именуемыми как «просто соседи». Линейными структурами данных могут быть табличный формат данных, текстовая информация и так далее. Их противоположностью могут считаться нелинейные структуры данных, у которых компоненты расположены в порядке различных иерархических уровней и делятся на следующие типы:
- Тип начальных компонентов.
- Тип выработанных компонентов.
- Тип компонентов, которые являются аналогами, то есть подобные компоненты.
Графом является нелинейная структура данных. Сам термин граф происходит из греческого языка и может быть переведён как «пишу». Всё вышеизложенное означает, что основным предназначением графа может считаться описание совокупности отношений, входящих в него компонентов.
Среди основных понятий теории графов необходимо отметить термин «инцидентность», на котором основываются все остальные термины. Две вершины графа считаются инцидентными, если они соединяются ребром. Если в какой-либо вершине берёт начало или заканчивается ребро, то это ребро и вершина могут считаться инцидентными. Разные виды графов могут иметь отличия между собой по типу вершин и (или) рёбер, которые входят в состав графов. Графы, у которых рёбра обладают направлением (направленные рёбра), именуются ориентированными. Если это условие не выполняется, то граф является неориентированным. Определение инцидентности может потребоваться при формировании алгоритмов решения отдельных задач из сферы информатики на базе теории графов. К примеру, в случае, если требуется осуществить реализацию обхода графа в глубину, а граф представлен матрицей инцидентности. В этом случае используется простое предположение, которое заключается в том, что движение может выполняться только по вершинам графа, между которыми имеются соединяющие их рёбра. Если при этом все рёбра ещё имеют «вес» (как правило, в числовом виде), то это позволяет разрешать задачи, имеющие повышенную сложность и прикладной характер.
По этой причине не стоит удивляться, что теория графов является одной из самых используемых методик при реализации искусственного интеллекта, поскольку искусственный интеллект может дискутировать практически с каждым условным объектом на практически любую тему, а также обсуждать наиболее приемлемые методики решения разнообразных задач. При этом он исполняет все эти операции без предварительных переключений и перенастроек, без которых даже человек не всегда может обходиться.
Типовой расчет по графам
Первой работой по практическому применению теории графов является задача с Кёнигсбергскими мостами. В условии указана река, а также омываемые рекой острова, и определённое количество мостов. Необходимо определить, имеется ли возможность при старте из исходной точки, пройти по каждому из мостов только один раз и вернуться в исходный пункт. Блок-схема задачи изображена на рисунке ниже:
Рисунок 1. Блок-схема задачи. Автор24 — интернет-биржа студенческих работ
Эту задачу можно смоделировать следующим образом. К каждому участку на берегу следует прикрепить по одной точке, а пару точек необходимо соединять линией только тогда, когда участки суши соединены при помощи моста. В результате получится граф, имеющий следующий вид:
Рисунок 2. Граф. Автор24 — интернет-биржа студенческих работ
Известный математик Эйлер выдал следующую формулировку ответа на такую задачу. Если бы у этой задачи могло быть решение, то в сформированном графе обязан существовать замкнутый маршрут, проходящий по рёбрам и содержащий каждое ребро только один раз. Если существует подобный маршрут, то каждая из вершин обязана обладать чётным количеством, что в приведённом примере не исполняется.
Формирование графов может также потребоваться для определения взаимосвязей компонентов внутри множества. Рассмотрим это обстоятельство на конкретном примере. Имеется множество А = {а1, а2, ... аn}, которое обозначает определённое человеческое сообщество, где все его составляющие изображены в виде точек. Имеется также множество В = {b1, b2, ... bm}, которое призвано отобразить взаимосвязи среди людей, то есть это линии, имеющие разную конфигурацию. В множестве «А» задаются взаимосвязи между людьми этого множества. Необходимо сформировать граф, который сможет отобразить все точки и связи, объединяющие их. Связи, то есть, линии, должны проходить между теми двумя людьми, которые знают друг друга. Очевидно, что количество знакомств у любого человека будет различным, и, возможно, существуют такие люди, которые вообще не знакомы ни с одним человеком. Их следует обозначать точками, от которых не должны отходить соединяющие линии. В итоге может быть реализован граф, имеющий следующий вид:
Рисунок 3. Граф. Автор24 — интернет-биржа студенческих работ
Точки графа являются его вершинами, а соединяющие их линии называются рёбрами графа.
В теории графов не принято учитывать фактическую специфику множеств А и В. На практике есть очень много самых разных проблемных задач, для решения которых можно временно не учитывать фактическое наполнение множеств и составляющих их элементов. Конкретные значения не оказывают влияния на процесс решения задачи, не зависимо от её сложности. Например, при определении маршрута передвижения из точки А в точку В, при соблюдении условия перемещения только по соединительным линиям между точками, не играет роли, что будет перемещаться в действительности, человек, автомобиль и тому подобное. Но в результате нужно найти решение, которое будет истинным для любого содержания, наполняющего структурную организацию графа.
