«Сетевые структуры данных. Понятие графа и его представления.»

ОБЩАЯ ТЕОРИЯ
Актуальность темы исследования
С развитием информационных технологий и увеличением объемов обрабатываемых данных возрастает потребность в эффективных способах организации и хранения информации. Одним из наиболее распространенных и универсальных методов представления данных являются сетевые структуры данных, основанные на понятии графа. В связи с этим, изучение сетевых структур данных и их представление является актуальным направлением исследований.
Цель и задачи исследования
Целью данной работы является изучение сетевых структур данных, а именно понятия графа, его видов и методов представления. Для достижения данной цели необходимо решить следующие задачи:
– Изучить понятие графа, его основные характеристики и виды;
– Рассмотреть различные способы представления графов;
– Проанализировать преимущества и недостатки каждого способа представления;
– Разработать алгоритм для реализации одного из способов представления графов.
Теоретическая часть
Понятие графа и его основные характеристики
Граф - это математическая структура, представляющая собой множество вершин и набор ребер, соединяющих эти вершины. Граф может быть ориентированным или неориентированным, содержать петли и кратные ребра.
Основными характеристиками графа являются количество вершин, ребер, связность, степень вершин и связность.
Виды графов
Существует множество видов графов, которые классифицируются по различным признакам. Например, графы могут быть ориентированными или неориентированными, связными или несвязными, регулярными или нерегулярными. Важными видами графов являются: дерево, взвешенный граф, мультиграф, псевдограф и другие.


гЛАВА 1. Основные понятия теории графов
Несколько примеров дадут немного поверхностного представления о графе. Так типичным графом является схема метро или какой-либо другой маршрут. В частности, программисту знакома компьютерная сеть, также являющаяся графом. Общее здесь это наличие точек, соединенных линиями. Так в компьютерной сети точки – это отдельные серверы, а линии – различные виды электрических сигналов. В метрополитене точки – станции, линии – туннели, проложенные между ними. В теории графов точки именуется вершинами, а линии – ребрами (дугами). Таким образом, граф – это совокупность вершин, соединённых ребрами.
Математика оперирует не содержанием вещей, а их структурой, абстрагируя ее из всего того, что дано как целое. Пользуясь именно этим приемом, мы можем заключать о каких-либо объектах как о графах. А поскольку теория графов — это часть математики, то для нее нет абсолютно никакого значения, что в принципе представляет собой объект; важно лишь то, является ли он графом, т. е. обладает ли обязательными для графов свойствами. Поэтому, прежде чем привести примеры, мы выделяем в рассматриваемом объекте лишь то, что как нам кажется, позволит показать аналогию, отыскиваем общее.
Вернемся к компьютерной сети. Она обладает определенной топологией, и может быть условно изображена в виде некоторого числа компьютеров и путей их соединяющих. В качестве примера показана полносвязная топология (Рисунок 1).

Рисунок 1 – Полносвязная топология предоставленная в виде графа

Пять компьютеров являются вершинами, а соединения (пути передачи сигналов) между ними – ребрами. Заменив компьютеры вершинами, мы получим математический объект – граф, который имеет 10 ребер и 5 вершин. Пронумеровать вершины можно произвольным образом, а не обязательно так, как это сделано на рисунке. Стоит отметить, что в данном примере не используется ни одной петли, то есть такого ребра, которое выходит из вершины и сразу же входит в нее, но петли могут встречаться в задачах.