2.1. 1. Если все вершины графа четные, то можно одним росчерком (т.е. не отрывая карандаша от бумаги и не проводя дважды по одной и той же линии) начертить граф. При этом движение можно начать с любой вершины и окончить в той же вершине. 2. Граф с двумя нечетными вершинами тоже можно начертить одним росчерком. Движение нужно начинать от любой нечетной вершины, а заканчивать на другой нечетной вершине. 3. Граф с более чем двумя нечетными вершинами невозможно начертить одним росчерком. 4. Число нечетных вершин графа всегда четное. 5. Если в графе имеются нечетные вершины, то наименьшее число росчерков, которыми можно нарисовать граф будет равно половине числа нечетных вершин этого графа.
3. История
3.1. Впервые основы теории графов появились в работах Леонарда Эйлера, в которых он описывал решение головоломок и математических развлекательных задач. Теория графов началась с решения Эйлером задачи о семи мостах Кёнигсберга
4. Виды
4.1. Ориентированные - графы, рёбрам которых присвоено направление
4.2. Неориентированные - множество вершин и набор рёбер, то есть соединений между парами вершин
4.3. Дерево - граф, в котором каждое ребро это мост
4.4. Полный - граф, в котором каждая пара различных вершин смежна
5. Способы представления
5.1. Матрица инцидентности - в ней указываются связи между ребрами) и вершинами. Столбцы матрицы соответствуют ребрам, строки — вершинам
5.2. Матрица смежности - это квадратная матрица размера n, в которой значение элемента aij равно числу рёбер из i-й вершины графа в j-ю вершину
