Графы можно классифицировать по количеству рёбер и вершин следующим образом:
По количеству вершин выделяют, например:
- Пустой граф. 1 У такого графа нет вершин и рёбер. 1
- Тривиальный граф. 1 У него есть только одна вершина и нет рёбер. 1
- Регулярный граф. 1 У каждой вершины одинаковое количество соседей. 1
По количеству рёбер выделяют, например:
- Полный граф. 14 Каждая пара вершин соединена ребром. 1
- Насыщенный граф. 4 Количество рёбер близко к максимально возможному. 4
- Разреженный граф. 4 Количество рёбер близко к количеству вершин в графе. 4
Также есть понятие степени вершины — это количество рёбер, для которых она является концевой (при этом петли считают дважды). 2 Изолированная вершина не имеет рёбер (её степень равна 0). 3