Сборник понятий

Материал из OSTIS_GT
Перейти к: навигация, поиск

Полезные ссылки: википедия - глосарий по теории графов словарь по теории графов

Примечание: Зачернутое понятие обозначает, что для него добавлен тикет на trac

Приглашаю к добавлению тикетов. Если тикет есть, то необходимо зачеркнуть понятие. Давайте как-нить работать =)

Содержание

Классы графовых структур

Важные

  • антисимметрический граф
  • бихроматический граф
  • вершинно непересекающийся граф
  • k-вершинно-связный граф
  • вершинно-симметрический граф
  • взвешенный граф
  • гамильтонов граф
  • гамильтоново-связный граф
  • геодезический граф
  • строго геодезический граф
  • гипогамильтоновый граф
  • двудольный граф
  • индифферентный граф
  • корневой граф
  • кубический граф
  • минимально связный граф
  • нечетный граф
  • однородный граф = регулярный граф
  • односторонне связный граф (односторонний граф)
  • одноциклический граф
  • ориентируемый граф
  • планарный граф (плоский граф)
  • полный граф
  • полный двудольный граф
  • полугамильтонов граф
  • полуэйлеров граф
  • помеченный граф
  • прогрессивно конечный граф
  • прогрессивно ограниченный граф
  • произвольно вычерчиваемый граф
  • произвольно гамильтонов граф
  • произвольно проходимый граф
  • простой граф
  • прямоугольный граф
  • псевдосимметрический граф
  • пустой граф (вполне несвязный граф, регулярный степени 0 граф)
  • разборный граф
  • раскрашенный граф
  • реберно раскрашиваемый граф
  • расщепляемый граф
  • реберно-критический граф
  • реберно k -раскрашиваемый граф
  • расширенный нечетный граф
  • реберно-регулярный граф
  • реберно-симметрический граф
  • реберный граф
  • регрессивно конечный граф
  • регрессивно ограниченный граф
  • регуляризуемый граф
  • регулярный граф
  • реконструируемый граф
  • самодополнительный граф
  • самонегативный граф
  • сбалансированный граф
  • сводимый граф
  • связный граф
  • k -связный граф
  • 2-секционный граф
  • сильно ориентированно-циклически замкнутый граф
  • сильно ориентированно-циклически-реберный граф
  • сильно связный граф (взаимно связный граф)
  • сильно-циклически замкнутый граф
  • сильно-циклически связный граф
  • симметрический граф
  • слабо связный граф
  • слабый орграф
  • смешанный граф
  • совершенный граф
  • соединяющий граф
  • соотнесенный неориентированный граф
  • составной граф
  • степенно-хордальный граф
  • строго хордальный граф
  • структурный граф
  • стягиваемый граф
  • счетный граф
  • топологический граф
  • S -топологический граф
  • тороидальный граф
  • тотальный граф
  • транзитивно ориентируемый граф
  • транзитивный граф
  • k -транзитивный граф
  • триангулированный граф
  • тривиальный граф
  • узловой граф
  • унитарный граф
  • k -унитранзитивный граф
  • унициклический граф
  • упорядоченный граф
  • управляющий граф
  • хордальный граф
  • хордальный двудольный граф
  • k -хроматический граф
  • цветной граф Кэлли
  • циклически жесткий граф
  • циклически замкнутый граф
  • циклический граф
  • циркулянтный граф
  • частичный граф
  • четный граф
  • эйлеров граф

Малозначительные

  • аранжируемый граф
  • асимметрический граф
  • бесконечный граф
  • бесконтурный граф
  • вершинно-критический граф
  • внешнепланарный граф
  • внешнеплоский граф
  • выпуклый прямолинейный граф
  • геометрически двойственный граф
  • дважды хордальный граф
  • двойственно хордальный граф
  • двойственный граф
  • двусторонний граф
  • дистанционно наследуемый граф
  • дистанционно-транзитивный граф
  • звездно-экстремальный граф
  • звездный граф
  • индуктивный граф
  • информационный граф
  • конечный граф
  • критический граф
  • максимальный сильно сингулярный граф
  • максимальный сингулярный граф
  • неразделимый граф
  • неразложимый граф
  • несводимый граф
  • несепарабельный граф
  • общий граф
  • обыкновенный граф
  • однозначно раскрашиваемый граф
  • ориентированно-циклически замкнутый граф
  • панциклический граф
  • полунесводимый граф
  • пороговый граф
  • почти однородный граф
  • правильный граф
  • префиксный граф ширины n

Отношения

Отношения над графовыми структурами

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

Отношения между графовыми сруктурами и их компонентами

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

Не отсортированные понятия и отношения:

  • маршрут;
  • путь;
  • гамильтонов путь;
  • гамильтонов цикл;
  • эйлерова цепь;
  • минимальное остовное дерево;
Личные инструменты