Презентация, доклад к занятию кружка по математике по теме: Графы(6 класс)

задач теории графов
Заключение

Схема кёнигсбергских мостов

например, граф Лев
Николаевич Толстой. В математике граф –
набор точек, некоторые из которых
соединены линиями. Точки именуются
вершинами графа, а отрезки – рёбрами.
На рисунке изображен граф, хорошо знакомый
москвичам. Это схема московского метро:
вершины – конечные станции и станции
пересадок, ребра – пути, соединяющие эти станции.

означает граф, в котором нет циклов, то есть в котором нельзя из некоторой вершины пройти по нескольким различным ребрам и вернуться в ту же вершину. Генеалогическое дерево будет деревом и в смысле теории графов, если в этом семействе не было браков между родственниками. На рисунке приведена часть генеалогического дерева греческих богов. Здесь его вершины – члены этого рода, а связывающие их отрезки – отношения родственности, ведущие от родителей к детям.

рёбрам в любую другую вершину
 

а рёбра связывают вершину с теми вершинами-ситуациями, которые могут сложиться после очередного хода

одного и того же множества не соединены между собой рёбрами.

взаимно однозначное соответствие, при котором вершинам, соединённым ребром, соответствуют вершины, также соединённые ребром.

река омывает два острова. С берегов на острова были перекинуты семь мостов. Издавна среди жителей была распространена такая загадка: как пройти по всем мостам, не проходя ни по одному из них дважды.
В 1736 году решая эту задачу Леонард Эйлер смог найти правило пользуясь которым легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них




Упрощённая схема мостов Граф кёнигсбергских мостов
Кёнигсберга
На упрощённой схеме части города (графе) мостам соответствуют линии (рёбра графа), а частям города - точки соединения линий (вершины графа). В ходе рассуждений Эйлер пришёл к следующим выводам:
Число нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа всегда чётно. Невозможно начертить граф, который имел бы нечётное число нечётных вершин.
Если все вершины графа чётные, то можно, не отрывая карандаша от бумаги, начертить граф, при этом можно начинать с любой вершины графа и завершить его в той же вершине.
Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком.
Император Кайзер Вильгельм решил задачу о кёнигсбергских мостах по своему. Он приказал построить ещё один мост. А задачу с восемью мостами теперь мог решить даже ребёнок.

Графы часто используют для решения логических проблем, связанных с перебором вариантов.








Однако для шахмат и шашек такой граф будет очень большим, поскольку различные позиции в этих играх исчисляются миллионами. А вот для игры «крестики – нолики» на доске 3 * 3 соответствующий граф нарисовать не так уж трудно, хотя и он будет содержать несколько десятков (но не миллионов) вершин.
Свойства графов не зависят от того, соединены вершины отрезками или кривыми линиями. Это дает возможность изучения их свойств с помощью одной из молодых наук – топологии, хотя сами задачи теории графов являются типичными задачами комбинаторики.

путь по ребрам графа, проходящий по каждому ребру ровно один раз.

– наименьшее количество красок, с помощью которых можно так раскрасить вершины графа, что любые две вершины, соединенные ребром, окрашиваются при этом в разные цвета. Каково хроматическое число для этого графа?

бригаде машинистом, кондуктором и кочегаром. Профессии их названы не обязательно в том же порядке, что и фамилии. В поезде, который обслуживает бригада, едут трое пассажиров с теми же фамилиями. В дальнейшем каждого пассажира мы будем почтительно называть «мистер»
2. М-р Робинсон живет в Лос-Анджелесе.
3. Кондуктор живет в Омахе.
4. М-р Джонс давно позабыл всю алгебру, которой его учили в колледже.
5. Пассажир – однофамилец кондуктора живет в Чикаго.
6. Кондуктор и один из пассажиров, известный специалист по математической физике, хотя в одну церковь.
7. Смит всегда выигрывает у кочегара, когда им случается встречаться за партией в бильярд.
Как фамилия машиниста?

на основании которых сделаны ходы (выводы).
Далее следует из п.7, что кочегар не Смит, следовательно, Смит – машинист.

с помощью графов. Знание основ теории графов необходимо в различных областях, связанных с управлением производством, бизнесом.