Факультативное занятие по математике в 6 классе Одинаковые графы. Эйлеровы графы

Муниципальное автономное общеобразовательное учреждение «Средняя общеобразовательная школа с углублённым изучением отдельных предметов № 3» Факультативное занятие по математике в 6 классе «Одинаковые графы. Эйлеровы графы» Учитель математики Сальникова Елена Петровна Березники 2015 г

Два графа будем называть одинаковыми, если выполнены следующие два условия: 1. у них равное число вершин, 2. вершины каждого графа можно пронумеровать так, что если вершины с номерами i и j соединены ребрами в одном графе, то вершины с теми же номерами соединены таким же числом рёбер и в другом графе, а если вершины с номерами i и j не соединены ребром в одном графе, то вершины с теми же номерами не соединены и в другом графе.

Благодаря этой рекламе сайт может продолжать свое существование, спасибо за просмотр.

Найдите все наборы одинаковых графов:

Можно ли начертить данные графы одним росчерком (не отрывая руки от бумаги и не проходя по ребру дважды)?

Такие графы, которые можно начертить, не отрывая карандаша от бумаги, называются уникурсальными (от латинского unus cursus – один путь), или эйлеровыми.

Какой граф невозможно начертить одним росчерком (не отрывая ручки от бумаги и не проводя никакое ребро дважды).

Граф с более чем двумя вершинами нечётной степени невозможно начертить одним росчерком (не отрывая ручки от бумаги и не проводя никакое ребро дважды).