Как называется граф, вершины которого соединены дугами?

Граф, в котором вершины соединены дугами, называется ориентированным графом или направленным графом. В ориентированном графе каждая связь между вершинами имеет направление, то есть каждая пара соединённых вершин имеет начало и конец. Направленные связи между вершинами называются дугами (или рёбрами), и они представляются упорядоченными парами вершин.

Основные характеристики ориентированного графа:

1. Ориентация: Каждая дуга имеет направление, которое указывает от одной вершины к другой. Например, если у нас есть дуга (A, B), это означает, что есть направление от вершины A к вершине B.

2. Степени вершин: В ориентированном графе различают входящую и исходящую степень вершины. Входящая степень — это количество дуг, которые заканчиваются в данной вершине, а исходящая — количество дуг, которые начинаются в этой вершине.

3. Представление: Ориентированные графы могут быть представлены различными способами, такими как списки смежности, матрицы смежности и матрицы инцидентности. В таких представлениях учитывается направление дуг.

4. Применение: Ориентированные графы широко используются в компьютерных науках и других областях для моделирования различных систем, где важен порядок или направление взаимодействий. Примеры включают графы дорог с односторонним движением, сети передачи данных, а также различные алгоритмические задачи, такие как поиск путей и циклов в графах.

Ориентированные графы являются важным инструментом в математике и информатике, позволяя моделировать и анализировать структуры, в которых взаимодействия между элементами имеют направленный характер.

Такой граф называется ориентированным графом или диграфом. В ориентированном графе каждая дуга имеет направление, то есть указывает на направление от одной вершины к другой. Ориентированные графы широко используются в различных областях информатики, таких как теория графов, сетевое моделирование, алгоритмы и т. д.