Решение задач с помощью графов
В последнее время интерес к комбинаторике в школьном курсе математики заметно возрос. Элементы комбинаторики, статистики и теории вероятностей включены в новые стандарты по математике для основной и профильной школ. Формирование комбинаторных представлений и развитие комбинаторного мышления школьников входит в число основных целей обучения математике. Однако обычно, когда говорят об элементах комбинаторики, имеют в виду задачи алгебраического содержания. Здесь мы рассмотрим комбинаторные задачи, которые можно решать с помощью графов. Пусть задано некоторое непустое множество V и множество E пар различных элементов из V. Элементы множества V называются вершинами графа, элементы множества E – ребрами графа. Множество вершин и множество ребер называют графом. Будем использовать геометрическое представление графа. Вершины графа изображаются в виде точек на плоскости. Если две вершины образуют ребро, то соответствующую пару точек соединяют линией. Например, на рис.1 изображен граф G, заданный множеством вершин V={1,2,3,4,5} и множеством ребер E ={(1,2), (2,3), (4,3), (4,2)} Число ребер, выходящих из вершины v, называют степенью вершины v и обозначается d(v). Вершина степени 0 называется изолированной, вершина степени 1 – висячей. 0≤ d(v) ≤ n-1, где n- число вершин графа. Рис.1
