Перейти на главную страницу
Поиск по сайту

Теория графов задачи с решением

Графами были названы схемы, состоящие из точек и соединяющих эти точки отрезков прямых или кривых примеры графов изображены на рисунке 1. С помощью графов часто упрощалось решение задач, сформулированных в различных теория графов задачи с решением знаний: в автоматике, электронике, физике, химии и др. С помощью графов изображаются схемы дорог, газопроводов, тепло- и теория графов задачи с решением. Помогают графы в решении математических и экономических задач. Познакомимся с основными понятиями теории графов при решении несложной задачи. Владимир, Григорий и Дмитрий при встрече обменялись рукопожатиями каждый пожал руку каждому по одному разу. Сколько всего рукопожатий было сделано? Пусть каждому из пяти молодых людей соответствует определенная точка на плоскости, названная первой теория графов задачи с решением его имени рис. Нулевой граф с пятью вершинами Неполный граф с пятью вершинами Точки А, Б, В, Г, Д называются вершинами графа, а отрезки линий, соединяющие эти точки — ребрами графа. При изображении графов на рисунках или схемах отрезки могут быть прямолинейными или криволинейными; Длины отрезков и расположение точек произвольны. Например, все три фигуры на рисунке изображают один и тот же граф. Рассмотрим процесс соединения точек А, Б, В, Г, Д ребрами. Ситуация, соответствующая моменту, когда рукопожатия еще не совершались, представляет собой точечную схему, изображенную на рисунке 2. Такая схема, состоящая из «изолированных» вершин, называется нулевым графом. Ситуация, когда совершены еще не все рукопожатия, может схематически быть изображена, например, с помощью рисунка З: пожали руки А и Б, А и Г, Д и Г, В и Следующий момент, когда добавятся, например, пожатия рук А и В, Г и Б, попробуйте изобразить сами. Графы, в которых не построены все возможные ребраназываются неполными графами. На рисунке 4 изображен граф, соответствующий всем совершенным рукопожатиям. Этот граф является полным графом. Полный граф с пятью вершинами Если подсчитать число ребер графа, изображенного на рисунке 4, то это число и будет равно теория графов задачи с решением совершенных рукопожатий между пятью молодыми людьми. Так, например, на рисунке 3 изображен неполный граф с пятью вершинами. На рисунке 4 ребра превращающие граф в полный граф изображены другим цветом, совокупность вершин графа с этими ребрами называется дополнением графа.


Другие статьи на тему:



 
Copyright © 2006-2016
avgplus.ru