Элементы теории графов. Способы обхода графов статья по информатике и икт (11 класс) по теме
Любая система, предполагающая наличие дискретных состояний или наличие узлов и переходов между ними может быть описана графом. Первая работа по теории графов, принадлежащая известному швейцарскому математику Л. Эйлеру, появилась в 1736 г. Эйлер решал очень известную головоломку о мостах Кёнигсберга. Термин «граф» впервые был введен спустя 200 лет (в 1936 г) Д. Кениго. Толчок к развитию теория графов получила на рубеже ХIX и ХХ столетий, когда резко возросло число работ в области топологии и комбинаторики, с которыми ее связывают самые тесные узы родства. Графы стали использоваться при построении схем электрических цепей и молекулярных схем. Как отдельная математическая дисциплина теория графов была впервые представлена в работе венгерского математика Кенига в 30-е годы ХХ столетия. В последнее время графы и связанные с ними методы исследований органически пронизывают на разных уровнях едва ли не всю современную математику. Графы эффективно используются в теории планирования и управления, теории расписаний, социологии, экономике, биологии, медицине, географии. Широкое применение находят графы в таких областях, как программирование, электроника, в решении вероятностных и комбинаторных задач, нахождения кратчайшего расстояния, максимального паросочетания и др. Математические развлечения и головоломки тоже являются частью теории графов. Теория графов быстро развивается, находит все новые приложения. Язык графов оказывается удобным для описания многих физических, технических, экономических, биологических, социальных и других систем.
Скачать:
ВложениеРазмер grafy.doc 709.5 КБ graffy_prezentaciya.ppt 1.56 МБПредварительный просмотр:
Лицей – интернат естественных наук
Любая система, предполагающая наличие дискретных состояний или наличие узлов и переходов между ними может быть описана графом.
Первая работа по теории графов, принадлежащая известному швейцарскому математику Л. Эйлеру, появилась в 1736 г. Эйлер решал очень известную головоломку о мостах Кёнигсберга. Термин «граф» впервые был введен спустя 200 лет (в 1936 г) Д. Кениго. Толчок к развитию теория графов получила на рубеже ХIX и ХХ столетий, когда резко возросло число работ в области топологии и комбинаторики, с которыми ее связывают самые тесные узы родства. Графы стали использоваться при построении схем электрических цепей и молекулярных схем.
Как отдельная математическая дисциплина теория графов была впервые представлена в работе венгерского математика Кенига в 30-е годы ХХ столетия.
В последнее время графы и связанные с ними методы исследований органически пронизывают на разных уровнях едва ли не всю современную математику. Графы эффективно используются в теории планирования и управления, теории расписаний, социологии, экономике, биологии, медицине, географии. Широкое применение находят графы в таких областях, как программирование, электроника, в решении вероятностных и комбинаторных задач, нахождения кратчайшего расстояния, максимального паросочетания и др. Математические развлечения и головоломки тоже являются частью теории графов. Теория графов быстро развивается, находит все новые приложения.
Язык графов оказывается удобным для описания многих физических, технических, экономических, биологических, социальных и других систем.
1. Основные понятия
Декартовым произведением двух множеств A и B называется множество пар элементов, таких, что первый элемент пары берется из множества A, второй из B: A x B = .
Например, декартовым произведением множеств A = и B = является множество A x B = < (0, a), (0, b), (0, c), (1, a), (1, b), (1, c)>.
Граф — это пара G = (V, E), где V – множество вершин, E – множество ребер (дуг).
Граф — совокупность конечного числа точек, называемых вершинами графа, и попарно соединяющих некоторые из этих вершин линий, называемых ребрами или дугами графа.
Вершины графа обозначают латинскими буквами A, B, C, D или цифрами. Иногда граф в целом можно обозначать одной заглавной буквой.
Неупорядоченная пара вершин называется ребром, упорядоченная – дугой . То есть отрезок между вершинами, имеющий направление, называют дугой . Направление обозначается стрелочкой на конце.
Отрезок между вершинами, не имеющий направления, называют ребром .
Дуги – это как дороги с односторонним движением: можно проехать только в одну сторону. Ребра – это как дороги с двусторонним движением: можно проехать в обе стороны.
Благодаря использованию графов можно упростить решение задач, сформулированных в различных областях знаний: в автоматике, электронике, физике, химии и др. С помощью графов изображаются схемы дорог, газопроводов, тепло- и электросети. Помогают графы в решении математических и экономических задач.
Аркадий, Борис. Владимир, Григорий и Дмитрий при встрече обменялись рукопожатиями (каждый пожал руку каждому по одному разу). Сколько всего рукопожатий было сделано?
Точки А, Б, В, Г, Д называются вершинами графа, а отрезки линий, соединяющие эти точки — ребрами графа.
В задаче необходимо подсчитать число ребер графа, изображенного на рисунке. Это число и будет равно количеству совершенных рукопожатий между пятью молодыми людьми. Их 10.
Граф, содержащий только дуги, называется ориентированным.
Ориентированным называется граф, в котором — множество упорядоченных пар вершин вида (x, y), где x – называется началом, y – концом дуги. Дугу (x, y) часто записывают как и изображают в виде:
Считается, что дуга ведет от вершины x к вершине y, а вершина y смежная с вершиной x. Ориентированный граф также называют орграфом.