- Граф – это геометрическая фигура, состоящая из точек и соединяющих их линий. Графы представляют объекты и связи между ними.
- Точки называются вершинами, а линии – рёбрами.
- Степенью вершины графа называется количество выходящих из нее рёбер.
- Вершина, имеющая чётную степень, называется чётной вершиной, соответственно, вершина, имеющая нечётную степень, называется нечётной вершиной.
- Примеры задач, решаемых с помощью графов:
- соединить технику проводами, по определённым условиям;
- доказать, что из одного города можно добраться в любой другой n путями;
- нарисовать граф, не отрывая карандаш от бумаги;
- доказать, что из столицы можно долететь в определённый город, при условии, что задано количество линий полёта.
