Графами называют геометрические фигуры, состоящие из точек (их называют вершинами) и соединяющих их линий (их называют рёбрами) С помощью вершин изображают элементы множества (предметов, людей, чисел), а с помощью рёбер – связи между ними
ВГ Б 1 А Полный граф. Задача 1: Андрей, Борис, Виктор и Григорий играли в шахматы. Каждый сыграл с каждым по одной партии. Сколько партий было сыграно ? В полном графе проводятся все возможные рёбра. Ответ: ?
Задача 2: Андрей, Борис, Виктор и Григорий обменялись фотографиями, причём каждый подарил каждому по одной фотографии. Сколько всего фотографий было подарено? ВГ Б 1 А Ответ: ? С помощью стрелок на рёбрах полного графа показан процесс обмена фотографиями.
Задача 3: Сколько диагоналей можно провести в выпуклом n-угольнике ? A1A1 A2A2 A3A3 AnAn n-угольник с диагоналями - это полный граф с n вершинами. Найдём число его рёбер: n * (n-1)/2.Тогда число диагоналей на n меньше и равно n * (n-1)/2-n = n * (n-3)/2 Ответ: n=n*(n-3)/2
Граф – дерево. Задача 4: В столовой на выбор предложено 3 первых, 2 вторых и 4 третьих блюда. Сколько различных обедов можно составить? 1-е блюдо2-е блюдо 3-е блюдо
1-е блюдо2-е блюдо3-е блюдо Дерево вариантов
Задача 5: Антон, Борис, и Василий купили 3 билета на футбол на 1-е, 2-е и 3-е места первого ряда. Сколькими способами они смогут занять свои места? А А В А В Б Б В Б Б А В В Б А Ответ: ?способов
Таким образом, графы представляют собой удобные схемы для изображения всех вариантов и определения их количества. Задачи для самостоятельного решения: 1.При встрече каждый из друзей пожал другому руку. Сколько рукопожатий было сделано, если друзей было: 1)трое; 2)четверо; 3)пятеро ? 2. Маше на день рождения подарили 3 букета цветов: розы, астры и гвоздики. В доме было 2 вазы: хрустальная и кера- мическая. Перечислить все возможные сочетания букета с вазой. 3. Сколько различных трёхзначных чисел можно записать с помощью цифр 5, 6, 7, 8, 9 при условии, что цифры в числе 1)могут повторяться; 2)должны быть различными?