Граф (титул)

Классификация графов

Графы делятся на

связные

несвязные

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

В несвязном графе существует хотя бы одна вершина, не связанная с другими.

Графы также подразделяются на

ориентированные

неориентированные

смешанные

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

В неориентированном графе по каждому из ребер можно осуществлять переход в обоих направлениях.

Частный случай двух этих видов – смешанный граф. Он характерен наличием как ориентированных, так и неориентированных ребер.

История термина

Русское слово граф заимствовано из нем. Graf, этимологически восходящего к зап.-герм. *ǥ(a)rēƀjōn > др.-фриз. grēva, др.-исл. greifi, ср.-нем. grêve; происхождение зап.-германского слова неизвестно. Впервые встречается в IX веке в латинских рукописях в формах grafio, graphio. Западногерманское слово употреблялось для перевода латинского comes «спутник», получившего в Средневековье значение «спутник короля» > «граф», откуда ст.-фр. cuens, косв. падеж conte (< лат. comitem) > фр. comte «граф».

Интересно проследить эволюцию слова в английском языке. Общегерманская основа в древнеанглийском звучала как ġerēfa (из ġe + *rēfa — и предположительно этимологизируется как «со-надзиратель, со-управляющий»). Впоследствии древняя общегерманская форма эволюционировала в две формы — grave (предположительно заимствовано из датского) и исконно английскую форму reeve. В русском языке последняя форма известна в виде shire-reeve (этимологически от scir — удел, надел + reeve — надзиратель) или в русской транскрипции — шериф.

Документ, удостоверяющий право на владение и управление территорией или доходным местом назывался graphiо, что можно перевести, как писание или грамота. Полученные на откуп доходные территории поступали в полное распоряжение графа, который становился по сути деловым партнёром законного владельца — короля. Сочетание «спутник короля» следует рассматривать в смысле делового партнерства. Такая практика была перенесена и на русские княжества в ордынский период, когда ярлык Великого хана давал русским князьям право на самоуправление при условии своевременного выполнения платёжных обязательств.

Способы представления графа в информатике

Матрица смежности

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

Это наиболее удобный способ представления плотных графов.

Недостатком являются требования к памяти, прямо пропорциональные квадрату количества вершин.

Двумерный массив;
Матрица с пропусками;
Неявное задание (при помощи функции).

Матрица инцидентности

Таблица, где строки соответствуют вершинам графа, а столбцы соответствуют связям (рёбрам) графа.
В ячейку матрицы на пересечении строки i{\displaystyle i} со столбцом j{\displaystyle j} записывается:

1: в случае, если связь j{\displaystyle j} «выходит» из вершины i{\displaystyle i},
−1,: если связь «входит» в вершину,; во всех остальных случаях (то есть если связь является петлёй или связь не инцидентна вершине)

Данный способ является довольно ёмким (размер пропорционален |V||E|{\displaystyle |V||E|}) для хранения, поэтому применяется очень редко, в особых случаях (например, для быстрого нахождения циклов в графе).

Список смежности

Список, где каждой вершине графа соответствует строка, в которой хранится список смежных вершин. Такая структура данных не является таблицей в обычном понимании, а представляет собой «список списков».

Размер занимаемой памяти: O(|V|+|E|){\displaystyle O(|V|+|E|)}.

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

Список рёбер

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

Размер занимаемой памяти: O(|E|){\displaystyle O(|E|)}.

Это наиболее компактный способ представления графов, поэтому часто применяется для внешнего хранения или обмена данными.

Языки описания

Для описания графов, пригодного для машинной обработки и одновременно удобного для человеческого восприятия, используется несколько стандартизированных языков, среди которых:

DOT
GraphML
Trivial Graph Format
GML
GXL
XGMML
DGML

Программы для построения

Разработана серия коммерческих программ для построения графов, так, построение графов лежит в основе прикладных программных пакетов фирмы ILOG (с 2009 года принадлежит корпорации IBM), среди других программ — GoView, Lassalle AddFlow, LEDA (есть бесплатная редакция).

Также существует свободная программа для построения графов igraph и свободная библиотека Boost.

Программы для визуализации

Для визуализации графов применяются следующие программные средства:

Graphviz (Eclipse Public License)
LION Graph Visualizer.
Графоанализатор — русскоязычная программа, с простым пользовательским интерфейсом (GNU LGPL; только для Windows).
Gephi — графическая оболочка для представления и изучения графов (GNU GPL, CDDL).
Библиотека GraphX — свободная библиотека для .NET для расчёта и отрисовки графов, использует WPF 4.0.
Библиотека MSAGL — свободная библиотека для .NET.

История термина

Документ, удостоверяющий право на владение и управление территорией или доходным местом назывался graphiо, что можно перевести, как писание или грамота. Полученные на откуп доходные территории поступали в полное распоряжение графа, который становился по сути деловым партнером законного владельца — короля. Сочетание «спутник короля» следует рассматривать в смысле делового партнерства. Такая практика была перенесена и на русские княжества в ордынский период, когда ярлык Великого хана давал русским князьям право на самоуправление при условии своевременного выполнения платежных обязательств.

Обзор областей применения графов

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

С высоты птичьего полета области применения графов можно разделить на две части:

технологии организации транзакционных графовых хранилищ, как правило, используемых в режиме реального времени непосредственно из приложения

Эти технологии называются графовыми базами данных, и им в этой книге будет уделено основное внимание. Они являются аналогом «нормальной» обработки транзакций в масштабе реального времени (On-Line Transaction Processing, OLTP) реляционных баз данных.
технологии автономного анализа графов, обычно реализующие серии пакетных шагов

Эти технологии часто называют механизмами вычисления графов (graphcomputeengine).Их можно отнести к той же категории, что и другие приемы анализа объемных данных, например интеллектуальный анализ данных и аналитическая обработка данных в реальном времени (OnLine Analytical Processing, OLAP).

Вас заинтересует / Intresting for you:

Citizen Integrator — что это … 1463 просмотров Дэн Sun, 07 Oct 2018, 08:29:12

Дэйв Кинчен (Dave Kinchen) — … 4536 просмотров Дэн Sun, 05 Aug 2018, 16:21:01

Исследование причин вибраций д… 971 просмотров Александров Попков Fri, 09 Aug 2019, 16:39:12

Джеймс Форгн (James Forgy) — с… 4113 просмотров Antoni Sun, 05 Aug 2018, 16:21:01

Author: Aida

Другие статьи автора:

Что такое граф, классификация графов, реализация на C++

Граф – совокупность точек, соединенных линиями. Точки называются вершинами, или узлами, а линии – ребрами, или дугами.

Степень входа вершины – количество входящих в нее ребер, степень выхода – количество исходящих ребер.

Граф, содержащий ребра между всеми парами вершин, является полным.

Встречаются такие графы, ребрам которых поставлено в соответствие конкретное числовое значение, они называются взвешенными графами, а это значение – весом ребра.

Когда у ребра оба конца совпадают, т.е. оно выходит из вершины и входит в нее, то такое ребро называется петлей.

Что такое граф, классификация графов, реализация на C++

Модель графов с метками и свойствами

При обсуждении рис. 2 мы неформально представили самую популярную графовую модель — графовую модель с метками и свойствами . Графовая модель с метками имеет следующие характеристики:

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

Большинство считает, что графовая модель со свойствами является простой и интуитивно понятной. Но, несмотря на свою простоту, именно она используется в подавляющем большинстве случаев при применении графов для отображения данных.

Рис. 1.2 Опубликованные сообщения

Графы в Германии

На немецком	На русском	Комментарий/Этимология
Markgraf	Маркграф и произошедшее от него маркиз	от марка (нем. mark — пограничная провинция) + граф. Дословно — граф марки.
Pfalzgraf	Пфальцграф (присутствует также в устар. английском palsgrave)	от рfalz (дворец) + граф. В Раннем Средневековье граф, управляющий пфальцем (дворцом) в период отсутствия в нём правящего монарха.
Reichsgraf	Рейхсграф	от нем. Reich — (Священная Римская) Империя + граф. Дословно — граф Империи
Landgraf	Ландграф	от land (земля) + граф. Титул графа, который пользовался в своих владениях высшей юрисдикцией и не был подчинен герцогу или князю. Гефюрстетер ландграф — военный наместник князя.
Freigraf	Фрейграф	от frei (свободный) + граф. Дословно — вольный граф
Gefürsteter Graf	Гефюрстетер граф	от нем. фюрст + граф. Изначально служащий князя, наместник. Буквально — княжий граф, то есть граф, вассальный непосредственно самому князю-фюрсту, в отличие от рейхсграфа (см. выше). В средневековой титулатуре граф стоял ниже герцога и князя.
Burggraf	Бургграф	от нем. burg (замок, крепость, местечко) + граф
Rheingraf	Рейнграф	от Rhein (река Рейн) + граф. Имя графов Рейнской области. Один из феодальных титулов древнейших западно-немецких династий. Только к концу Средних веков этот титул стал понемногу исчезать
Altgraf	Альтграф	от alt (старый) + граф. Один из феодальных титулов древнейших западно-немецких династий. Только к концу Средних веков этот титул стал понемногу исчезать.
Wildgraf	Вильдграф	от wild (с нем. — «дичь» в значении «дикая, неосвоенная местность») + граф. Один из феодальных титулов древнейших западно-немецких династий. Только к концу Средних веков этот титул стал понемногу исчезать, благодаря постоянной борьбе с лотарингскими герцогами и архиепископами Трирским и Кельнским.
Raugraf	Рауграф	от rau (необжитое место, нетронутое) + граф
Vizegraf	Виконт	от vize (заместитель) + граф

Графы в России

См. также: Список графских родов Российской империи

Первые пожалования графами в России исходили от императора Священной Римской империи (1701 − Ф. А. Головин, 1702 − А. Д. Меншиков, 1707 − Г. И. Головкин, 1715 − А. А. Матвеев).

Первый граф России Ф. А. Головин(Памятная монета Банка России)

Первым титул графа от русского царя получил Б. П. Шереметев () за подавление Астраханского восстания. Затем Петром I пожалованы Г. И. Головкин (1709), П. М. и Ф. М. Апраксины, Н. М. Зотов и И. А. Мусин-Пушкин (1710), Я. В. Брюс (1721), А. М. Апраксин (1722), П. А. Толстой (1724).

Графские роды подразделялись на российские (125 родов, в том числе графы Царства Польского и Великого княжества Финляндского), графское достоинство которых достигалось либо пожалованием (последним титул получил В. Б. Фредерикс), либо присоединением с разрешения императора титула и фамилии родственного (свойственного) графского рода, не имевшего прямых потомков мужского пола (например, Кушелёвы-Безбородко (1816), Сумароковы-Эльстон (1856), Головкины-Хвощинские (1895)), а также иностранные. Эти в свою очередь делились на российские роды, получившие титул иностранных государств (например, братья Зубовы (1793, Римская империя) и иностранные графские роды, принявшие российское подданство (например, Красинские (1837, Франция), Горны (1860, Швеция), Нессельроде (1705, Римская империя), Ностицы (1849, Силезия), Подгорчиани (1769, Венеция). Графское достоинство являлось наследственным, однако в исключительных случаях могло быть личным (К. М. Пржездзецкий, 1843). В ряде случаев, за особые отличия, награждение титулом могло сопровождаться добавлением (как особого пожалования) к фамилии почётной приставки (Муравьёв-Амурский (1858), Паскевич-Эриванский (1828), Суворов-Рымникский (1789). Графы титуловались «ваше сиятельство»; графские роды вносились в 5-ю часть дворянских родословных книг. К 1894 году было учтено 310 родов (в том числе около 70 пресёкшихся в мужской линии).

Графы в России

Первые пожалования графами в России исходили от императора Священной Римской империи (1701 − Ф. А. Головин, 1702 − А. Д. Меншиков, 1707 − Г. И. Головкин, 1715 − А. А. Матвеев). Первым титул графа от русского царя получил Б. П. Шереметев () за подавление Астраханского восстания. Затем Петром I пожалованы Г. И. Головкин (1709), П. М. и Ф. М. Апраксины Н. М. Зотов и И. А. Мусин-Пушкин (1710), Я. В. Брюс (1721), А. М. Апраксин (1722), П. А. Толстой (1724).

Способы представления графа в информатике

Матрица смежности

Основная статья: Матрица смежности

Это наиболее удобный способ представления плотных графов.

Недостатком являются требования к памяти, прямо пропорциональные квадрату количества вершин.

Двумерный массив;
Матрица с пропусками;
Неявное задание (при помощи функции).

Матрица инцидентности

Основная статья: Матрица инцидентности

1: в случае, если связь j{\displaystyle j} «выходит» из вершины i{\displaystyle i},
−1,: если связь «входит» в вершину,; во всех остальных случаях (то есть если связь является петлёй или связь не инцидентна вершине)

Список смежности

Основная статья: Список смежности

Размер занимаемой памяти: O(|V|+|E|){\displaystyle O(|V|+|E|)}.

Список рёбер

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

Размер занимаемой памяти: O(|E|){\displaystyle O(|E|)}.

Языки описания

DOT
GraphML
Trivial Graph Format
GML
GXL
XGMML
DGML

Программы для построения

Также существует свободная программа для построения графов igraph и свободная библиотека Boost.

Программы для визуализации

Для визуализации графов применяются следующие программные средства:

Graphviz (Eclipse Public License)
LION Graph Visualizer.
Графоанализатор — русскоязычная программа, с простым пользовательским интерфейсом (GNU LGPL; только для Windows).
Gephi — графическая оболочка для представления и изучения графов (GNU GPL, CDDL).
Библиотека GraphX — свободная библиотека для .NET для расчёта и отрисовки графов, использует WPF 4.0.
Библиотека MSAGL — свободная библиотека для .NET.

Литература

Оре О. Теория графов. — М.: Наука, 1968. — 336 с.
Математический энциклопедический словарь, Прохоров Ю.В., 1988
Уилсон Р. Введение в теорию графов. — М.: Мир, 1977. — 208 с.
Харари Ф. Теория графов. — М.: Мир, 1973.
Кормен Т. М. и др. Часть VI. Алгоритмы для работы с графами // Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-е изд. — М.: Вильямс, 2006. — С. 1296. — ISBN 0-07-013151-1.
Салий В. Н., Богомолов А. М. Алгебраические основы теории дискретных систем. — М.: Физико-математическая литература, 1997. — ISBN 5-02-015033-9.
Касьянов В. Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. — СПб.: БХВ-Петербург, 2003. — С. 1104. — ISBN 5-94157-184-4.
Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. М.: Наука, 1990. 384с. (Изд.2, испр. М.: УРСС, 2009. 392 с.)
Кирсанов М. Н. Графы в Maple. — М.: Физматлит, 2007. — 168 с. — ISBN 978-5-9221-0745-7.
Графы // Энциклопедический словарь юного математика / Сост. А. П. Савин. — М.: Педагогика, 1985. — С. 86—88. — 352 с.

Обобщение понятия графа

Простой граф является одномерным симплициальным комплексом.

Более абстрактно, граф можно задать как тройку (V,E,φ){\displaystyle (V,E,\varphi )},
где V{\displaystyle V} и E{\displaystyle E} — некоторые множества (вершин и рёбер, соотв.),
а φ{\displaystyle \varphi } — функция инцидентности (или инцидентор), сопоставляющая каждому ребру
e∈E{\displaystyle e\in E} (упорядоченную или неупорядоченную) пару вершин u{\displaystyle u} и v{\displaystyle v} из V{\displaystyle V} (его концов). Частными случаями этого понятия являются:

ориентированные графы (орграфы) — когда φ(e){\displaystyle \varphi (e)} всегда является упорядоченной парой вершин;
неориентированные графы — когда φ(e){\displaystyle \varphi (e)} всегда является неупорядоченной парой вершин;
смешанные графы — граф, в котором встречаются как ориентированные, так и неориентированные рёбра и петли;
эйлеровы графы — граф, в котором существует циклический эйлеров путь (эйлеров цикл);
мультиграфы — графы с кратными рёбрами, имеющими своими концами одну и ту же пару вершин;
псевдографы — это мультиграфы, допускающие наличие петель;
простые графы — не имеющие петель и кратных рёбер.

Под данное выше определение не подходят некоторые другие обобщения:

гиперграф — если ребро может соединять более двух вершин.
ультраграф — если между элементами xi{\displaystyle x_{i}} и uj{\displaystyle u_{j}} существуют бинарные отношения инцидентности.

Способы представления графа

Граф может быть представлен (сохранен) несколькими способами:

матрица смежности;
матрица инцидентности;
список смежности (инцидентности);
список ребер.

Использование двух первых методов предполагает хранение графа в виде двумерного массива (матрицы). Размер массива зависит от количества вершин и/или ребер в конкретном графе.

Матрица смежности графа — это квадратная матрица, в которой каждый элемент принимает одно из двух значений: 0 или 1.

Число строк матрицы смежности равно числу столбцов и соответствует количеству вершин графа.

– соответствует отсутствию ребра,
1 – соответствует наличию ребра.

Матрица смежности графа

Когда из одной вершины в другую проход свободен (имеется ребро), в ячейку заносится 1, иначе – 0. Все элементы на главной диагонали равны 0 если граф не имеет петель.

Матрица инцидентности (инциденции) графа — это матрица, количество строк в которой соответствует числу вершин, а количество столбцов – числу рёбер. В ней указываются связи между инцидентными элементами графа (ребро(дуга) и вершина).

В неориентированном графе если вершина инцидентна ребру то соответствующий элемент равен 1, в противном случае элемент равен 0.

В ориентированном графе если ребро выходит из вершины, то соответствующий элемент равен 1, если ребро входит в вершину, то соответствующий элемент равен -1, если ребро отсутствует, то элемент равен 0.

Матрица инцидентности для своего представления требует нумерации рёбер, что не всегда удобно.

Матрица инцидентности (инциденции) графа

Список смежности (инцидентности) Если количество ребер графа по сравнению с количеством вершин невелико, то значения большинства элементов матрицы смежности будут равны 0. При этом использование данного метода нецелесообразно. Для подобных графов имеются более оптимальные способы их представления.

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

Список смежности (инцидентности)

Преимущества списка смежности:

Рациональное использование памяти.
Позволяет быстро перебирать соседей вершины.
Позволяет проверять наличие ребра и удалять его.

Недостатки списка смежности:

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

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

Список рёбер

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

Графы в Германии

На немецком	На русском	Комментарий/Этимология
Markgraf	Маркграф и произошедшее от него маркиз	от марка (нем. mark — пограничная провинция) + граф. Дословно — граф марки.
Pfalzgraf	Пфальцграф (присутствует также в устар. английском palsgrave)	от рfalz (дворец) + граф. В Раннем Средневековье граф, управляющий пфальцем (дворцом) в период отсутствия в нём правящего монарха.
Reichsgraf	Рейхсграф	от нем. Reich — (Священная Римская) Империя + граф. Дословно — граф Империи
Landgraf	Ландграф	от land (земля) + граф. Титул графа, который пользовался в своих владениях высшей юрисдикцией и не был подчинен герцогу или князю. Гефюрстетер ландграф — военный наместник князя.
Freigraf	Фрейграф	от frei (свободный) + граф. Дословно — вольный граф
Gefürsteter Graf	Гефюрстетер граф	от нем. фюрст + граф. Изначально служащий князя, наместник. Буквально — княжий граф, то есть граф, вассальный непосредственно самому князю-фюрсту, в отличие от рейхсграфа (см. выше). В средневековой титулатуре граф стоял ниже герцога и князя.
Burggraf	Бургграф	от нем. burg (замок, крепость, местечко) + граф
Rheingraf	Рейнграф	от Rhein (река Рейн) + граф. Имя графов Рейнской области. Один из феодальных титулов древнейших западно-немецких династий. Только к концу Средних веков этот титул стал понемногу исчезать
Altgraf	Альтграф	от alt (старый) + граф. Один из феодальных титулов древнейших западно-немецких династий. Только к концу Средних веков этот титул стал понемногу исчезать.
Wildgraf	Вильдграф	от wild (с нем. — «дичь» в значении «дикая, неосвоенная местность») + граф. Один из феодальных титулов древнейших западно-немецких династий. Только к концу Средних веков этот титул стал понемногу исчезать, благодаря постоянной борьбе с лотарингскими герцогами и архиепископами Трирским и Кельнским.
Raugraf	Рауграф	от rau (необжитое место, нетронутое) + граф
Vizegraf	Виконт	от vize (заместитель) + граф

Обобщение понятия графа

Простой граф является одномерным симплициальным комплексом.

ориентированные графы (орграфы) — когда φ(e){\displaystyle \varphi (e)} всегда является упорядоченной парой вершин;
неориентированные графы — когда φ(e){\displaystyle \varphi (e)} всегда является неупорядоченной парой вершин;
смешанные графы — граф, в котором встречаются как ориентированные, так и неориентированные рёбра и петли;
эйлеровы графы — граф, в котором существует циклический эйлеров путь (эйлеров цикл);
мультиграфы — графы с кратными рёбрами, имеющими своими концами одну и ту же пару вершин;
псевдографы — это мультиграфы, допускающие наличие петель;
простые графы — не имеющие петель и кратных рёбер.

Под данное выше определение не подходят некоторые другие обобщения:

гиперграф — если ребро может соединять более двух вершин.
ультраграф — если между элементами xi{\displaystyle x_{i}} и uj{\displaystyle u_{j}} существуют бинарные отношения инцидентности.