7.----!!!!!!!!!!!!!!!!

8.----!!!!!!!!!!!!!!!!

9. Матрица инцидентности — одна из форм представления графа, в которой указываются связи между инцидентными элементами графа (ребро(дуга) и вершина). Столбцы матрицы соответствуют ребрам, строки — вершинам. Ненулевое значение в ячейке матрицы указывает связь между вершиной и ребром (их инцидентность).

В случае ориентированного графа каждому ребру <x,y> ставится в соответствие "-1" на позиции (x,y) и "1" на позиции (y,x); если связи между вершинами нет, то ставится в соответствие "0".

10. Степень вершины (англ. degree, также валентность, англ. valency) в теории графов — количество рёбер графа , инцидентныхвершине . При подсчёте степени ребро-петля учитывается дважды.^[1] Степень вершины обозначается как (в западных источниках — ). Максимальная и минимальная степень вершин графа G обозначаются соответственно Δ(G) и δ(G). На рис. 1 максимальная степень равна 5, минимальная — 0. В регулярном графе степени всех вершин одинаковы, поэтому в данном случае можно говорить о степени графа.

11. Матрица достижимости простого ориентированого графа  — бинарная матрица замыкания по транзитивности отношения (оно задаётся матрицей смежности графа). Таким образом, в матрице достижимости хранится информация о существовании путей между вершинами орграфа.

12. Клика - полный подграф неориентированного графа. Другими словами, клика графа есть подмножество его вершин, такое, что между каждой парой вершин этого подмножества существует ребро и, кроме того, это подмножество не принадлежит никакому большему подмножеству с тем же свойством.

13. Цикломатическое число графа — минимальное число ребер, которые надо удалить, чтобы граф стал ациклическим. Для связного графа существует соотношение:где— цикломатическое число,— числокомпонент связности графа, — числорёбер, а — числовершин.

14. Центр графа — множество вершин , для которых справедливо равенство:, где— это эксцентриситет вершины, а— радиус графа.

15. Диаметр графа — это максимум расстояния между вершинами для всех пар вершин. Расстояние между вершинами — наименьшее число рёберпути, соединяющего две вершины.

16. Радиус графа — минимальный из эксцентриситетов вершин связного графа; вершина, на которой достигается этот минимум, называется центральной вершиной.

17. Мост (в теории графов) — ребро, удаление которого увеличивает количество компонент связности.

18. Независимое множество вершин (известное также как внутренне устойчивое множество) есть множество вершин графа G, такое, что любые две вершины в нем не смежны (никакая пара вершин не соединена ребром).

    Независимое множество называется максимальным, когда нет другого независимого множества, в которое оно бы входило.

19. Планарний граф — граф, який може бути зображений на площині без перетину ребер.

Граф зображений на площині називається плоским, якщо його ребра не перетинаються. Граф називається планарним, якщо він ізоморфний деякому плоскому графу. Тобто існує відображення вершин графа на деякі точки площини і ребер графа на прості криві у площині, так що кінцями кривих є точки, що відповідають вершинам ребра і дві різні криві не мають спільних точок, окрім можливо кінцевих.

20. Хроматическое число графа — минимальное число , такое что множествовершин графа можно разбить нанепересекающихся классов:

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