Граф — математическая абстракция реальной системы любой природы, объекты которой обладают парными связями. Граф как математический объект есть совокупность двух множеств — множества самих объектов, называемого множеством вершин, и множества их парных связей, называемого множеством рёбер. Элемент множества рёбер есть пара элементов множества вершин.
Графы находят широкое применение в современной науке и технике. Они используются и в естественных науках (физике и химии) и в социальных науках (например, социологии), но наибольших масштабов применение графов получило в информатике и сетевых технологиях.
В качестве простейшего примера из жизни можно привести схему перелётов определённой авиакомпании, которая моделируется графом, где вершинами графа являются города, а рёбрами — рейсы, соединяющие пары городов. Дерево каталогов в компьютере также является графом: диски, папки и файлы являются вершинами, а рёбра показывают вложенность файлов и папок в папки и диски[1]. Строение Википедии моделируется ориентированным графом, в котором статьи — вершины графа, а гиперссылки — дуги (тематическая карта).
Графы являются основным объектом изучения теории графов.
Простой граф
Определение. Простой граф {\displaystyle G(V,E)} G(V,E) есть совокупность двух множеств – непустого множества {\displaystyle V} V и множества {\displaystyle E} E неупорядоченных пар различных элементов множества {\displaystyle V} V . Множество {\displaystyle V} V называется множеством вершин, множество {\displaystyle E} E называется множеством рёбер
{\displaystyle G(V,E)=\left\langle V,E\right\rangle ,\quad V\neq \varnothing ,\quad E\subseteq V\times V,\quad \left\{v,v\right\}\notin E,\quad v\in V} {\displaystyle G(V,E)=\left\langle V,E\right\rangle ,\quad V\neq \varnothing ,\quad E\subseteq V\times V,\quad \left\{v,v\right\}\notin E,\quad v\in V},
то есть множество {\displaystyle E} E состоит из 2-элементных подмножеств множества {\displaystyle V} V.
Пример диаграммы неориентированного графа
https://ru.wikipedia.org/wiki/Граф_(математика)