Графов теория

Графов теория
граф с шестью вершинами и семью рёбрами

Тео́рия гра́фов — раздел дискретной математики, изучающий свойства графов. В общем смысле граф представляется как множество вершин (узлов), соединённых рёбрами. В строгом определении графом называется такая пара множеств G={R,V}, где V есть подмножество любого счётного множества, а R — подмножество V×V.

Теория графов находит применение, например, в геоинформационных системах (ГИС). Существующие или вновь проектируемые дома, сооружения, кварталы и т. п. рассматриваются как вершины, а соединяющие их дороги, инженерные сети, линии электропередач и т. п. — как рёбра. Применение различных вычислений, производимых на таком графе, позволяет, например, найти кратчайший объездной путь или ближайший продуктовый магазин, спланировать оптимальный маршрут.

Теория графов содержит большое количество нерешённых проблем и пока недоказанных гипотез.

Содержание

История возникновения теории графов

Родоначальником теории графов считается Леонард Эйлер. В 1736 году в одном из своих писем он формулирует и предлагает решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов.

Терминология теории графов

Терминология теории графов поныне не определена строго. В частности в монографии Гудман, Хидетниеми, 1981 сказано: «В программистском мире нет единого мнения о том, какой из двух терминов „граф“ или „сеть“. Мы выбрали термин „сеть“, так как он, по-видимому, чаще встречается в прикладных областях». Аналогичная ситуация для «вершина/точка»

Изображение графов на плоскости

При изображении графов чаще всего используется следующая система обозначений: каждой вершине сопоставляется точка на плоскости, и если между вершинами существует ребро, то соответствующие точки соединяются отрезком. В случае ориентированного графа отрезки заменяют стрелками.

Не следует путать изображение графа с собственно графом (абстрактной структурой), поскольку одному графу можно сопоставить не одно графическое представление. Изображение призвано лишь показать, какие пары вершин соединены рёбрами, а какие — нет. Часто на практике бывает трудно ответить на вопрос, являются ли два изображения моделями одного и того же графа или нет. В зависимости от задачи, одни изображения могут давать более наглядную картину, чем другие.

Некоторые задачи теории графов

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

Применение теории графов

Литература

  • Химические приложения топологии и теории графов. Под ред. Р. Кинга. Пер. с англ. М.: Мир, 1987.

См. также

Ссылки


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Полезное


Смотреть что такое "Графов теория" в других словарях:

  • ГРАФОВ ТЕОРИЯ — раздел математики, особенность которого геометрический подход к изучению объектов. Основное понятие теории граф задается множеством вершин (точек) и множеством ребер (связей), соединяющих некоторые пары вершин. Пример графа схема метрополитена:… …   Большой Энциклопедический словарь

  • Графов теория —         раздел конечной математики (См. Конечная математика), особенностью которого является геометрический подход к изучению объектов. Основное понятие теории граф. Граф задаётся множеством вершин (точек) и множеством рёбер (связей), соединяющих …   Большая советская энциклопедия

  • графов теория — раздел математики, особенность которого  геометрический подход к изучению объектов. Основное понятие теории  граф  задаётся множеством вершин (точек) и множеством рёбер (связей), соединяющих некоторые пары вершин. Пример графа  схема… …   Энциклопедический словарь

  • ГРАФОВ ТЕОРИЯ — область дискретной математики, особенностью к рой является геометрич. подход к изучению объектов. Основной объект Г. т. граф и его обобщения. Первые задачи Г. т. были связаны с решением математических развлекательных задач и головоломок (задача о …   Математическая энциклопедия

  • ГРАФОВ ТЕОРИЯ — в химии, область конечной математики, изучающая дискретные структуры, наз. графами; применяется для решения различных теоретич. и прикладных задач. Некоторые основные понятия. Граф совокупность точек (вершин) и совокупность пар этих точек (не… …   Химическая энциклопедия

  • ГРАФОВ ТЕОРИЯ — (THEORY OF GRAPHS) раздел математики, изучающий свойства разл. графов. Наиболее раннее упоминание о графах встречается в работе Л.Эйлера (1736). Окончательно как матем. дисциплина Г.т. оформилась в 1936 г. после выхода монографии Д. Кенига Теория …   Глоссарий терминов по грузоперевозкам, логистике, таможенному оформлению

  • ГРАФОВ ТЕОРИЯ — раздел математики, особенность к рого геом. подход к изучению объектов. Осн. понятие теории граф задаётся множеством вершин (точек) и множеством рёбер (связей), соединяющих нек рые пары вершин. Пример графа схема метрополитена: множество станций… …   Большой энциклопедический политехнический словарь

  • ГРАФОВ ТЕОРИЯ — раздел математики, особенность к рого геом. подход к изучению объектов. Осн. понятие теории граф задаётся множеством вершин (точек) и множеством рёбер (связей), соединяющих нек рые пары вершин. Пример графа схема метрополитена: множество станций… …   Естествознание. Энциклопедический словарь

  • Теория чисел — Теория чисел, или высшая арифметика раздел математики, изучающий целые числа и сходные объекты. В теории чисел в широком смысле рассматриваются как алгебраические, так и трансцендентные числа, а также функции различного происхождения, которые… …   Википедия

  • Теория надёжности — Теория надёжности  наука, изучающая закономерности распределения отказов технических устройств, причины и модели их возникновения. Теория надёжности изучает методы обеспечения стабильности работы объектов (изделий, устройств, систем и т …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
… Нажмите правой клавишей мыши и выберите «Копировать ссылку»