Внаслідок розвитку природничих наук, програмування предмет теорії графів набув такого широкого спектру застосування, що він потребує відповіої уваги шкільного курсу математики. Оскількі теорія графів не входить до шкільної програми з математики, то в умовах завдань не буває слова «граф». Протє завдання з теорії графів легко впізнавані – це задачі на: знайомства і обмін, вибір або відповідність, маршрути, спортивні турніри, мости, комбінаторні завдання.
Теорія графів – дисципліна математична, тому її виклад включає і необхідні строгі визначення. Отже, приступимо до організованого введення основних понять цієї теорії.
Граф – це сукупність кінцевого числа точок і ліній, що попарно сполучають деякі з цих точок (є більш строге визначення, але на практиці воно не потрібне). Ці точки називаються вершинами, а лінії, що сполучають їх, називаються ребрами графа або дугами графа.
Число ребер, що виходять з вершини графа називають степінью цієї вершини. Вершина графа, що має непарну степінь, називається непарною, а що має парну степінь парною.
Завантажити файл