Общие сведения | Энциклопедия | Научные публикации | Публицистика | Новости | Каталоги | Авторы |
| На главную | О проекте | Контакты | | |
![]() |
|
Статья в Энциклопедическом Фонде
Граф![]()
Граф - конечная совокупность вершин, некоторые из которых соединены ребрами.
Объекты представляются как вершины, или узлы графа, а связи - как дуги, или рёбра. Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или рёбрах. Теория графов - раздел дискретной математики, изучающий свойства графов. В строгом определении графом называется такая пара множеств G={R,V}, где V есть подмножество любого счётного множества, а R - подмножество. Терминология теории графов поныне не определена строго. В частности в монографии Гудман, Хидетниеми, 1981 сказано "В программистском мире нет единого мнения о том, какой из двух терминов "граф" или "сеть". Графы обычно изображаются в виде геометрических фигур, так что вершины графа изображаются точками, а ребра - линиями, соединяющими точки. Граф называется ориентированным (или орграфом),если некоторые ребра имеют направление. Это означает, что в орграфе некоторая вершина может быть соединена с другой вершиной, а обратного соединения нет. Геометрически граф часто изображают точками плоскости, причем соседние вершины соединены дугами (для орграфа некоторые дуги имеют направление, что обычно отмечают стрелкой). Помимо этого, в теории графов рассматриваются также мультиграфы - это такие графы, в которых могут быть петли (т. е. некоторая вершина соединена сама с собой ребром) или некоторые пары вершины могут быть соединены между собой несколькими ребрами. Маршрут в графе - последовательность соседних (смежных) вершин. Ясно, что можно определить маршрут и как последовательность смежных ребер (в этом случае ребра приобретают направление). Заметим, что в маршруте могут повторяться вершины, но не ребра. Маршрут называется циклом, если в нем первая вершина совпадает с последней. Путь в графе (иногда говорят простой путь) - это маршрут без повторения вершин (а значит, и ребер). Контур - цикл без повторения вершин, за исключением первой вершины, совпадающей с последней. Петля это дуга, начальная и конечная вершина которой совпадают. Простой граф - без кратных ребер и петель. Степень вершины это удвоенное количество петель, находящихся у этой вершины плюс количество остальных прилегающих к ней ребер. Пустым называется граф без ребер. Полным называется граф, в котором каждые две вершины смежные. Граф называется: * связным, если для любых вершин u, v есть путь из u в v. * сильно связным или ориентированно связным, если он ориентированный, и из любой вершины в любую другую имеется ориентированный путь. * деревом, если он связный и не содержит простых циклов. * полным, если любые его две (различные, если не допускаются петли) вершины соединены ребром. * двудольным, если его вершины можно разбить на два не пересекающихся подмножества V1 и V2 так, что всякое ребро соединяет вершину из V1 с вершиной из V2. * k-дольным, если его вершины можно разбить на k не пересекающихся подмножества V1, V2, ..., Vk так, что не будет рёбер, соединяющих вершины одного и того же подмножества. * полным двудольным, если каждая вершина одного подмножества соединена ребром с каждой вершиной другого подмножества. * планарным, если граф можно изобразить диаграммой на плоскости без пересечений рёбер. * взвешенным, если каждому ребру графа поставлено в соответствие некоторое число, называемое весом ребра. * хордальным, если граф не содержит индуцированных циклов с длиной больше трех. Графы широко используются во многих областях науки и техники, в частности: * Файловая система компьютера. Иерархия файлов и папок во многих операциних системах имеет вид дерева, которое является частным случаем графа; * Молекулы всех химических веществ можно изобразить в виде графа, где атомы являются вершинами, а связи между ними - ребрами; * Карта автомобильных или любых других путей также является графом, причем каждая дорога может иметь определенное значение "веса" (например, плотность транспортного потока), тогда такой граф является взвешенным; * Социальные сети также можно представить в виде графа, где каждая человека или социальная группа является вершиной, а связи между ними - ребрами; * Генеалогические деревья являются примером бинарных деревьев, что также является частным случаем графа; * Турнирные таблицы спортивных чемпионатов также могут быть изображены в виде графов; * В биологии и экологии графы также используются уже давно. Примерами могут быть цепи питания, экосистемы, генетические последовательности и карты таксономическая иерархия живых организмов и т.п.; * В археологии и геологии графы используются в стратиграфии для изучения геологических пластов; * Любой производственный процесс также может быть изображен с помощью графа; * Разработка программного обеспечения и компьютерные науки вообще является одной из тех отраслей, где графы применяются чаще. Сложность и большое количество модулей и протоколов в современных программных продуктах сильно затрудняет понимание их работы, управления ею и ее оптимизацию, поэтому очень часто складываются графы программ, причем зачастую это делается автоматически трансляторами или компиляторами. Графы также удобными для изображения структур данных, блок-схем, потоков данных, схем баз данных и баз знаний, конечных автоматов, схем компьютерных сетей и отдельных сайтов, схем вызовов подпрограмм и т.д.. Также графы широко используются во многих алгоритмах поиска и сортировки. Кроме того, одним из главных направлений современных исследований в области глобальных сетей является заданное консорциумом W3C задачи построения семантической сети (один из видов графов) на базе существующей сети Интернет. Используемые источники 1. Спекторский И.Я. Дискретная математика. - С. 220 c .. - "Политехника", 2004. ISBN 966-622-136-5. 2. JA Bondy, USR Murty Graph Theory With Applications. - С. 264 c .. - Elsevier / North-Holland, 1976. ISBN 0-444-19451-7. 3. Сик Дж., Ли Л., Ламсдэйн Э. C + + Boost Graph Library. - С. 304 c .. - Питер, 2006. ISBN 978-5-469-00352-6. 4. Березина Л. Ю. графы и их применение. - М. : URSS, 2009. - 152 с. 5. Берж К. Теория графов и ее применения. - М. : ИЛ, 1962. - 320 с. 6. Харари Ф. Теория графов. - М. : Мир, 1973. - 304 с. 7. Шенфилд Дж. Математическая логика. М.: Наука, 2005. |
|