Граф это что кратко

Обновлено: 05.07.2024

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

В России титул введён Петром I (первым его получил в 1706 году Б. П. Шереметев) [1] . В конце XIX века учтено свыше 300 графских родов. Графский титул в советской России был ликвидирован Декретом ВЦИК и Совнаркома от 11 ноября 1917 года.

Граф (нем. Graf ) — королевское должностное лицо в Раннем Средневековье в Западной Европе. Титул возник в IV веке в Римской империи и первоначально присваивался высшим сановникам (например, comes sacrarum largitionum — главный казначей). Во Франкском государстве со второй половины VI века граф (гауграф) в своём округе-графстве/гау (нем. Gau — первоначально, сельская община у древних германцев, численностью ок. 100 человек) обладал судебной, административной и военной властью. По постановлению Карла II Лысого (877) должность и владения графа стали наследственными.

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

В России титул введён Петром I (первым его получил в 1706 году Б. П. Шереметев). В конце XIX века учтено свыше 300 графских родов. Графский титул в советской России был ликвидирован Декретом ВЦИК и Совнаркома от 11 ноября 1917 года.

Содержание

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

См. также

— титул, от которого произошёл титул английских графов earl

Примечания

Литература

Wikimedia Foundation . 2010 .

Полезное

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

Граф (титул) — Граф (нем. Graf, лат. comes, франц. cornte, англ. earl), в раннее средневековье в Западной Европе королевское должностное лицо (во Франкском государстве Г. обладал со 2 й половины 6 в. в своём округе графстве судебной, административной, военной… … Большая советская энциклопедия

Граф титул — (немецк. Graf; старинные формы garafio, grafio, gerefa, greve; франц. comte, от лат. comes; англ. earl) в настоящее время титул, первоначально название должностного лица во Франкском государстве и в Англии. Этимология слова graf очень неясна.… … Энциклопедический словарь Ф.А. Брокгауза и И.А. Ефрона

Граф, титул — (немецк. Graf; старинные формы garafio, grafio, gerefa, greve; франц. comte, от лат. comes; англ. earl) в настоящее время титул, первоначально название должностного лица во Франкском государстве и в Англии. Этимология слова graf очень неясна.… … Энциклопедический словарь Ф.А. Брокгауза и И.А. Ефрона

Варвик (граф. титул) — (Warwick) английский графский титул, который носили разные дома и который был соединен с владением замком В. Этот замок, один из древнейших в Англии, был, по преданию, еще во времена англосаксов жилищем знаменитого в английских героических… … Энциклопедический словарь Ф.А. Брокгауза и И.А. Ефрона

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

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

Граф Мар — (англ. Earl of Mar) один из старинных дворянских титулов в Шотландии. Об их землях см. Марр (Шотландия). Содержание 1 История 2 Мормеры Мара … Википедия

Граф Марч — или Граф Марки (англ. Earl of March) титул, который несколько раз создавался в Англии и Шотландии для представителей семей, владения которых располагались пограничных владениях (марках) между Англией с Уэльсом (Валлийская марка) и Англией с… … Википедия

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  
  

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

  Алгоритмы обхода графов

  Основными алгоритмами обхода графов являются

  
  
  Поиск в ширину подразумевает поуровневое исследование графа:

  • вначале посещается корень – произвольно выбранный узел,
  • затем – все потомки данного узла,
  • после этого посещаются потомки потомков и т.д.

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

  • 0 — оранжевый – необнаруженная вершина;
  • 1 — зеленый – обнаруженная, но не посещенная вершина;
  • 2 — серый – обработанная вершина.

  Фиолетовый – рассматриваемая вершина.

  Применения алгоритма поиска в ширину

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

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

  
  Реализация на C++ (с использованием очереди STL)
  

  
  

  Результат выполнения
  

  Задача поиска кратчайшего пути
  Реализация на С++
  

  
  Результат выполнения
  
  

  
  
  Поиск в глубину – это алгоритм обхода вершин графа.

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

  Отсутствие последнего свидетельствует об одной из двух возможных ситуаций:

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

  Каждая вершина может находиться в одном из 3 состояний:

  • 0 - оранжевый – необнаруженная вершина;
  • 1 - зеленый – обнаруженная, но не посещенная вершина;
  • 2 - серый – обработанная вершина;

  Фиолетовый – рассматриваемая вершина.

  Применения алгоритма поиска в глубину

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

  Алгоритм поиска в глубину работает как на ориентированных, так и на неориентированных графах. Применимость алгоритма зависит от конкретной задачи.
  Для реализации алгоритма удобно использовать стек или рекурсию.

  
  Реализация на C++ (с использованием стека STL)
  

  
  

  Результат выполнения
  
  Задача поиска лексикографически первого пути на графе.
  Реализация на C++
  

  Результат выполнения
  
  

  Поиск в глубину также может быть реализован с использованием рекурсивного алгоритма.

  Реализация обхода графа в глубину на C++ (с использованием рекурсии)
  

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

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

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

  Что такое граф или теория графов для чайников

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

  Какие бывают графы

  
  

  Ориентированный граф — это граф, у которого направление ребер имеет существенное значение и поэтому ребра задаются со стрелками на конце, например:

  
  

  
  Иногда граф бывает смешанным, это когда часть ребер идет с обязательным направлением, а часть без направления. Такие графы редкие, но они есть, например:

  
  

  Какими еще бывают графы

  Математический граф может быть пустым — это когда он состоит только из одних вершин, даже без одного ребра. Например:

  
  

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

  
  

  Полный граф — это такой граф, вершины которого соединены между собой всеми доступными вариантами. То есть каждая отдельная вершина соединена со всеми вершинами графа, например:

  
  

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

  Гамильтов граф — это такой граф, у которого можно обойти все вершины графа, посетив каждую из них только один раз.

  
  

  Заключение

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

  Читайте также:

    
  • Для чего нужна словарная статья кратко
    
  • Какие подвиги они совершали и от кого ждали славы крестьянские дети кратко
    
  • Хлебников бобэоби анализ кратко
    
  • Почему сегодня в школе суета и шум и гам
    
  • Какая политика в сша получила название охоты на ведьм кратко