1. Познакомить слушающих с определением графа. 2. Понять, как решаются задачи с помощью графов. 3. Закономерности, которые необходимо соблюдать при решении задач с помощью графов. 4. Виды графов. 5. Где встречаются графы в жизни.

Графом называется конечное множество точек, некоторые из которых соединены линиями. Точки называются вершинами графа, а соединяющие линии – рёбрами. Графом называется конечное множество точек, некоторые из которых соединены линиями. Точки называются вершинами графа, а соединяющие линии – рёбрами.

Закономерность 1. Невозможно начертить граф с нечетным числом нечетных вершин. Закономерность 2. Если все вершины графа четные, то можно не отрывая карандаш от бумаги (« одним росчерком »), проводя по каждому ребру только один раз, начертить этот граф. Движение можно начать с любой вершины и закончить его в той же вершине. Закономерность 3. Граф, имеющий всего две нечетные вершины, можно начертить, не отрывая карандаш от бумаги, при этом движение нужно начать с одной из этих нечетных вершин и закончить во второй из них. Закономерность 4. Граф, имеющий более двух нечетных вершин, невозможно начертить « одним росчерком ». Граф, имеющий более двух нечетных вершин, невозможно начертить « одним росчерком ».

У Наташи есть 2 конверта : обычный и авиа, и 3 марки : прямоугольная, квадратная и треугольная. Сколькими способами Наташа может выбрать конверт и марку, чтобы отправить письмо ?

Схема метро Схема авиалиний

Вершины и ребра этих графов отвечают соответственно атомам и химическим связям между ними ( химия ). Схема электрической цепи ( физика )

Википедия Журнал « Математика в школе » – г Комбинаторика и теория графов. Носов В. А., Московский Государственный институт электроники и математики, 1999

СПАСИБО ЗА ВНИМАНИЕ !