Под неориентированным графом (или короче графом) будем понимать такую произвольную пару G = <V, E>, где V - множество вершин, E -рёбер.
Способы задания - матричный, аналитический, графический.
Если граф имеет цикл (необязательно простой), содержащий все рёбра графа по одному разу, то такой цикл называется эйлеровым циклом, а граф называется эйлеровым графом.
Определение. Полным графом называется граф с n вершинами без петель, кратных и противоположных дуг (ориентация безразлична), у которого любые две вершины соединены дугой.
Связность - имеет путь от вершины к вершине.
Цикломатическое число графа — минимальное число рёбер, которые надо удалить, чтобы граф стал ациклическим. Для связного графа существует соотношение: где — цикломатическое число, — число компонент связности графа, — число рёбер, а — число вершин.
Основное свойство цикломатического числа формулируется в виде теоремы: