ГРАФ это:

ГРАФ

- множество Vвершин и набор Енеупорядоченных и упорядоченных пар вершин; обозначается Г. через . Неупорядоченная пара вершин наз. ребром, упорядоченная пара - дугой. Г., содержащий только ребра, наз. неориентированным; Г., содержащий только дуги,- ориентированным. Пара вершин может соединяться двумя или более ребрами (дугами одного направления), такие ребра (дуги) наз. кратными. Дуга (или ребро) может начинаться и кончаться в одной и той же вершине, такая дуга (ребро) наз. петлей. (Иногда под Г. понимают Г. без петель и кратных ребер; тогда Г., в к-ром допускаются кратные ребра, наз. мультиграфом, а Г., в к-ром допускаются кратные ребра и петли, наз. псевдографом.)

Вершины, соединенные ребром или дугой, наз. смежными. Ребра, имеющие общую вершину, также наз. смежными. Ребро (дуга) и любая из его двух вершин наз. инцидентными. Говорят, что ребро соединяет вершины и , а дуга начинается в вершине ин кончается в вершине v.

Каждый Г. можно представить в евклидовом пространстве множеством точек, соответствующих вершинам, к-рые соединены линиями, соответствующими ребрам (или дугам) Г. В трехмерном пространстве любой Г. можно представить таким образом, что линии, соответствующие ребрам (дугам), не пересекаются во внутренних точках.

Существуют различные способы задания Г. Пусть - вершины графа - его ребра. Матрицей смежности, соответствующей графу G, наз. матрица у к-рой элемент равен числу ребер (дуг), соединяющих вершины и (идущих из в ), и , если соответствующие вершины не смежны. В матрице инцидентности графа Gэлемент , если вершина инцидентна ребру , и , если вершина и ребро не инцидентны. Г. можно задать посредством списков, напр., указанием пар вершин, соединенных ребрами (дугами), или заданием для каждой вершины множества смежных с ней вершин. Два графа и наз. изоморфными, если существует взаимно однозначное соответствие между множествами вершин V, W и множествами ребер сохраняющее отношение инцидентности (см. также Графов изоморфизм).

Подграфом графа наз. Г. с множеством вершин и множеством ребер (дуг) каждое из к-рых инцидентно только вершинам из . Подграфом порожденным подмножеством , наз. Г. с множеством вершин и набором ребер (дуг) , состоящим из всех ребер (дуг) графа G, к-рые соединяют вершины из .Остовный подграф содержит все вершины графа Gи нек-рый поднабор его ребер (дуг) Последовательность ребер наз. маршрутом, соединяющим вершины и . Маршрут замкнут, если . Маршрут наз. цепью, если все его ребра различны, и простой цепью, если все его вершины различны. Замкнутая (простая) цепь наз. (простым) циклом. Г. наз. связным, если любая пара его вершин соединена маршрутом. Максимальный связный подграф графа Gназ. компонентой связности. Несвязный Г. имеет по крайней мере две компоненты связности (см. также Графа связность).

Длина маршрута (цепи, простой цепи) равна количеству ребер в порядке их прохождения. Длина кратчайшей простой цепи, соединяющей вершины и в графе G, наз. расстоянием между и . В связном неориентированном Г. расстояние удовлетворяет аксиомам метрики. Диаметр Г.- это его наибольшее расстояние. Величина


наз. радиусом, а вершина , для к-рой

принимает наименьшее значение, наз. центром графа G. В Г. может быть много центров и ни одного.

Степенью вершины графа , обозначаемой di, наз. число ребер, инцидентных этой вершине. Если граф G (без петель) имеет пвершин и требер, то

Вершина наз. изолированной, если , и концевой, если . Г., у к-рого все вершины имеют одинаковые степени (равные k), наз. регулярным (степени k). В полном Г. нет петель и каждая пара вершин соединена в точности одним ребром. Для графа не имеющего петель и кратных ребер, дополнительным Г. к Gназ. граф , у к-рого и вершины смежны в только в том случае, когда они не смежны в G. Т., дополнительный к полному, состоит из изолированных вершин и наз. пустым. Многие характеристики для графа Gи его дополнения оказываются зависимыми. В ориентированном графе Gдля каждой вершины определяются полустепень исхода и полустепень захода как количества дуг, выходящих из этой вершины и входящих в нее соответственно. Полный ориентированный Г. наз. турниром.

Каждому графу G можно отнести ряд Г., являющихся производными от G. Так, реберным графом L (G) графа Gназ. Г., вершины к-рого соответствуют ребрам графа G и две вершины смежны в L(G) в том н только в том случае, когда соответствующие им ребра графа G смежны. В тотальном графе Т(G) графа G вершины соответствуют элементам графа G, т. е. вершинам и ребрам, и две вершины в Т(G).смежны тогда и только тогда, когда соответствующие элементы в G смежны или инцидентны. Многие свойства графа G переносятся на графы L(G).и T(G). Известно много обобщений понятия "Г."; одними из них являются понятия гиперграфа и сети.

С помощью различных операций можно строить Г. из более простых, переходить от одного Г. к более простому, разбивать Г. на более простые, в заданном классе Г. переходить от одного Г. к другому п т. д. Наиболее употребительными одноместными операциями являются: удаление ребра (вершины ребра сохраняются), добавление ребра между двумя вершинами Г., удаление вершины вместе с инцидентными ей ребрами (Г., полученный в результате удаления вершины из графа , часто обозначают ), добавление вершины (к-рую можно соединить ребрами с нек-рыми вершинами Г.), стягивание ребра - отождествление пары смежных вершин, т. е. удаление пары смежных вершин и добавление новой вершины, смежной с теми вершинами Г., к-рые были смежны хотя бы с одной из удаленных вершин; подразбиение ребра- удаление ребра и добавление новой вершины, к-рая соединяется ребром с каждой вершиной удаленного ребра. В ряде задач теории Г. используются двуместные операции над Г. Пусть и -Г. такие, что и Объединением графов и наз. граф " с множеством вершин и множеством ребер Произведением графов наз. граф множеством вершин к-рого являются элементы декартова произведения причем две из этих вершин () и () смежны в том и только в том случае, если либо и вершина смежна с вершиной , либо и вершина смежна с вершиной Напр., любой Г. является объединением своих компонент связности; Г., известный как n-мерный единичный куб , может быть определен рекуррентно с помощью операции произведения:


где -граф, состоящий из пары вершин, соединенных одним ребром. Эти операции можно определить также для пересекающихся Г., в частности для подграфов одного Г. Сложением по модулю 2 графов наз. граф G с множеством вершин и множеством ребер .


Употребляются и другие многоместные операции над Г. Для некоторых классов Г. удается найти простые операции, позволяющие с помощью много кратного их применения перейти от любого Г. изучаемого класса к любому другому Г. этого класса. На рис. 1 приведена операция, с помощью к-рой в классе Г. с одинаковым набором степеней можно перейти от одного произвольного Г. к любому другому; на рис. 2 показана операция, позволяющая в классе плоских триангуляции (см. Граф плоский).с одинаковым числом вершин перейти от произвольной триангуляции к любой другой. Для описания и изучения нек-рых классов Г. отыскиваются такие операции и множества Г., из к-рых с помощью данных операций можно получить любой Г. заданного класса. Операции над Г. используются также для построения Г. с заданными свойствами, при вычислении графов числовых характеристик и т. д.

Понятие "Г." используется в определении таких ма-тематич. понятии, как управляющая система, в нек-рых определениях алгоритма, грамматики и др. Изложение ряда математич. теорий становится более наглядным при использовании геометрич. представления Г., напр. теории марковских цепей. Понятие "Г." широко используется при создании п описании различных математич. моделей в экономике, биологии и т. д.

Лит.:[1] Берж К., Теория графов и ее применения пер. с франц., М., 1962; [2] Оре О., Теория графов, пер. с англ., M., 1968 [3] Зыков А. А..Теория конечных графов, [в. 1], Новосибирск., 1969; [4] Харари Ф., Теория графов, пер. с англ., М., 1973.


Математическая энциклопедия. — М.: Советская энциклопедия. . 1977—1985.

Синонимы:

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

  • граф — граф/ …   Морфемно-орфографический словарь

  • Граф — Граф: От древневерхненемецкого gravo, gravio «предводитель, вождь»: Граф (титул)  дворянский титул; «Граф»  короткометражная немая кинокомедия Чарли Чаплина (The Count, 1916). От греч. γράφω «царапаю, черчу, пишу»: Граф… …   Википедия

  • ...граф — I Конечная часть сложных имен существительных греческого происхождения, вносящая значение: специалист в сфере деятельности, названной в начальной части слова (библиограф, биограф, географ, топограф, этнограф и т.п.). II Конечная часть сложных… …   Современный толковый словарь русского языка Ефремовой

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

  • граф — Графическое изображение электрической цепи, в котором ветви электрической цепи представлены отрезками, называемыми ветвями графа, а узлы электрической цепи — точками, называемыми узлами графа. [ГОСТ Р 52002 2003] граф Основное понятие и… …   Справочник технического переводчика

  • граф — [титул] сущ., м., употр. часто Морфология: (нет) кого? графа, кому? графу, (вижу) кого? графа, кем? графом, о ком? о графе; мн. кто? графы, (нет) кого? графов, кому? графам, (вижу) кого? графов, кем? графами, о ком? о графах; сущ. графиня Граф …   Толковый словарь Дмитриева

  • ГРАФ — (нем. Graf) в раннем средневековье в Зап. Европе должностное лицо, представлявшее власть короля в графстве. В период феодальной раздробленности графы превратились в независимых крупных феодалов. В дальнейшем граф дворянский титул (в России со… …   Большой Энциклопедический словарь

  • граф — а; м. [нем. Graf] Дворянский титул выше баронского; лицо, носящее этот титул. ◁ Графиня, и; инь; ж. Графский, ая, ое. Г. титул. Г ие земли. * * * граф (нем. Graf), в раннее средневековье в Западной Европе должностное лицо, представляющее власть… …   Энциклопедический словарь

  • граф — См …   Словарь синонимов

  • Граф — [graph] основное понятие и объект изучения теории графов, математически определяется двояко. С одной стороны как совокупность двух множеств: множества элементов x Î X и множества соответствий, отношений между этими элементами t Î T. С другой… …   Экономико-математический словарь

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

Книги

Другие книги по запросу «ГРАФ» >>


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

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