Ядро (теория графов)

Ядро графа — это понятие, описывающее поведение графа в отношении гомоморфизмов графа.

Связанные понятия

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

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

Порождённый подграф графа — это другой граф, образованный из подмножества вершин графа вместе со всеми рёбрами, соединяющими пары вершин из этого подмножества.

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

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

Упоминания в литературе

Я попытаюсь заново сформулировать последнее требование без редукционистского уклона. Законы движения любой физической системы дают только условные предсказания и, следовательно, совместимы со многими возможными историями этой системы. (Этот вопрос не имеет отношения к ограничениям на предсказуемость, которые накладывает квантовая теория и о которых я расскажу в следующей главе). Например, законы движения, которым подчиняется ядро, выпущенное из пушки, совместимы со многими возможными траекториями, каждая из которых соответствует одному из возможных направлений и углов наклона ствола пушки при выстреле (рис. 1.2). Математически законы движения можно выразить системой уравнений, которые называют уравнениями движения. Существует много различных решений этих уравнений, каждое из которых описывает какую-то возможную траекторию. Чтобы определить, какое решение описывает фактическую траекторию, необходимо предоставить дополнительные данные – некоторую информацию о том, что происходит в действительности. Один из способов осуществить это заключается в описании начального состояния, в данном случае направления ствола пушки. Однако существуют и другие способы. Например, мы точно так же могли бы определить конечное состояние – положение и направление движения пушечного ядра в момент его приземления. Или мы могли бы определить положение самой высокой точки траектории. Неважно, какие именно дополнительные данные мы даем, если они позволяют выбрать одно конкретное решение системы уравнений движения. Объединение любых дополнительных данных такого рода с законами движения и дает теорию, которая описывает все, что происходит с пушечным ядром между моментами выстрела до падения.

Дэвид Дойч, Структура реальности. Наука параллельных вселенных, 1997

Фреге очень необычный мыслитель, поскольку его творческий поиск осуществлялся на стыке философии и математики. Свою главную задачу он видел в том, чтобы подвести под арифметику надежное логическое основание, продемонстрировав возможность определения ее основных понятий и аксиом в терминах чистой логики. Таким образом, Фреге первым выдвинул программу обоснования арифметики путем сведения ее к логике, которая получила название «логицизм». Для выполнения этой программы он создал совершенно новую логику, осуществив первое аксиоматическое построение пропозиционального исчисления и построив теорию квантификации и исчисление предикатов, которые образуют ядро современной математической логики. Эта новая логическая система была сформулирована Фреге на специально разработанном им формально-логическом языке. Задавая интерпретацию этого искусственного языка, Фреге заложил основы логической семантики, однако если в дальнейшем при создании логических языков стали четко отделять их синтаксис (задание словаря исходных символов, формулировка правил образования и преобразования выражений языка и т. п.) от семантики (сопоставление категориям языковых выражений различных типов внеязыковых сущностей), то Фреге выстраивает синтаксис и семантику своей системы одновременно по мере введения новых знаков и выражений. Более того, семантика языка формулируется им с учетом уже имеющейся онтологии внеязыкового мира, для представления которой и создается язык. Однако следует отметить, что Фреге не просто взял стандартную онтологию для арифметики, которая включает теорию чисел и математический анализ, но внес в нее существенные дополнения и изменения, по-новому осмыслив многие математические понятия, прежде всего понятия функции, класса и числа.

Л. Б. Макеева, Язык, онтология и реализм, 2011

С точки зрения структуры скрепы-фразы чрезвычайно разнообразны. В их роли могут выступать как не производные, как и производные союзы и их аналоги. Они выступают в качестве скреп, оформляющих сложное синтаксическое целое и реализующих грамматические отношения паратаксиса и гипотаксиса. Следует заметить, что гипотаксис является своеобразным «наследием» более простых, чем СТ, ярусов синтаксиса, подобных сложноподчиненному предложению. Отношения подчинения наиболее эксплицитно выражают минимальные категориальные и логические соотношения пропозиции в реализованных синтаксических структурах. В свою очередь, паратаксис как отношения равноправия не является столь важным для низших ярусов синтаксиса, поскольку он не формирует таких базовых единиц, как словосочетание и компоненты предложенческой структуры. Как правило, паратаксис является показателем семантического развертывания структурного ядра высказывания. Он показывает на наличие нескольких смысловых центров, зажимающих одну и ту же грамматическую позицию. Таким образом отношения паратаксиса наиболее пригодны для выражения смыслов больших, чем элементарная логическая единица и являются более характерными уже для тестового уровня, на котором встречается и взаимодействует большее количество пропозиций, которые в своем выражении могут являться синтаксически равноправными. Поскольку МФС выражает категориальные отношения текстового уровня, то ее смысловое наполнение может модифицироваться от релятивного к номинативному, то есть включать в себя некатегориальные компоненты смысла, сопоставимые с полноценным лексическим наполнением. Иными словами, целая грамматическая конструкция, имеющая относительную коммуникативную завершенность, может иметь доминирующее значение юнкционного характера, что переводит эту конструкцию в разряд грамматических средств связи.

О. И. Филимонов, Скрепа-фраза в языке, 2013

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

Л. С. Якунин, Философские вопросы науковедения, 2017

Качество 5 Большого Аркана на молекулярном уровне соответствует совокупности свойств ядра атома, как принципа, систематизирующего конфигурацию нейтронов и протонов. В биохимии следует рассматривать совокупность свойств ядер и их конфигурацию в организме.

Константин Добрев, ТАРО Иерофанта. Архитектура человека по системе ТАРО, 2016

В качестве иллюстрации рассмотрим дескриптор «химическая связь» из класса базовых понятий. Данный дескриптор характеризуется первым уровнем усвоения, предполагающим общее представление студента о данном понятии, умение давать определение понятию, то есть семантизировать его, при необходимости производить символьный перевод, то есть из словесной формы в форму символов, моделей, графиков и др. (прил. 7). При его изучении используются дескрипторы «ядро», «электрон», «электронная плотность», «ковалентная связь», «ионная связь», «металлическая связь», «химическое соединение».

Н. Ш. Мифтахова, Методология и методика адаптационного обучения химии на дуязычной основе в высшей школе, 2012

Здесь A=>B– обычная продукция "если … то …", которая носит название ядра продукции. Элемент Р характеризует внешние условия или условия применимости продукции, определяемые факторами, не входящими непосредственно в A, например, целями, которые стоят перед рассуждающей системой. Условия Р позволяют из всех продукций, у которых в левой части ядра стоит A, отбирать нужную часть продукций. Элемент П характеризует сферу проблемной области базы знаний, или предусловия применимости продукции. Эти предусловия ничем не отличаются от Р, но выделяют подсистемы продукций на ранг выше тех, которые выделяют условия. Предусловия задают формальную систему, в рамках которой будут проводиться логические рассуждения… Наконец, Q характеризует постусловия продукции, указывающие на те изменения, которые необходимо внести в базу знаний и в систему продукций после реализации данной продукции" [23, стр. 134-135].

Олег Варламов, Мивар: Линейный логический вывод

В современной науке любое исследование физических свойств времени все чаще связывается с принципами квантовой механики. Так, в картине мироздания физики вполне определенно выделяют минимальные размеры ячеек пространства, называя их «фундаментальной длиной» – квантами пространства. Предполагаемая величина этих гипотетических «атомов пространства» реально совершенно невообразима, она представляет собой дробь с 33 нулями в знаменателе. Если бы мы увеличили размер таких клеток пространства до одного сантиметра, то диаметр атома возрос бы до 30 миллиардов световых лет, в два раза превзойдя размер Метагалактики. Атом – это минимальный реально наблюдаемый в электронный микроскоп объект, следующий за ним на пути в глубины материи – атомное ядро. Если повторить увеличение, ядро атома превратится в галактику, свет по которой будет путешествовать 300 000 лет.

Олег Фейгин, Механика машины времени, 2016

– пирамида концентрирует энергию не только Солнца, но и «… витонное излучение ядра Земли, выходящее снизу и с юга. … Ради оптимального приема и преломления пирамидой излучения ядра планеты и соблюдалась такая высочайшая точность строительных работ» [4];

М. Ю. Трещалин, Энергетическая концепция жизни. Часть IV. Особенности пирамидальных конструкций. Энергоинформационные кристаллы. Пирамиды и христианство, 2016

Связанные понятия (продолжение)

Критерий планарности Уитни — это матроидное описание планарных графов. Критерий носит имя Хасслера Уитни. Критерий утверждает, что граф G планарен тогда и только тогда, когда его графовый матроид является также кографовым (то есть является двойственным матроидом другого графового матроида).

В теории графов под графом Клебша понимается один из двух дополняющих друг друга графов, имеющих 16 вершин. Один из них имеет 40 рёбер и является 5-регулярным графом, другой имеет 80 рёбер и является 10-регулярным графом. 80-рёберный вариант — это половинный граф куба 5-го порядка. Назван графом Клебша в 1968 году Зайделем ввиду его связи с конфигурацией прямых поверхности четвёртого порядка, открытой 1868 году немецким математиком Альфредом Клебшем. 40-рёберный вариант – это складной граф куба...

Подробнее: Граф Клебша

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

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

Расщепляемый граф может иметь несколько разложений на клику и независимое множество. Так, путь a-b-c является расщепляемым и может быть разбит тремя разными способами...

Сильная гипотеза о совершенных графах — это характеризация запрещёнными графами совершенных графов как в точности тех графов, которые не имеют ни нечётных дыр (порождённых циклов нечётной длины), ни нечётных антидыр (дополнений нечётным дырам). Гипотезу высказал Берж в 1961. Доказательство Марии Чудновской, Нила Робертсона, Пола Сеймура и Робина Томаса было заявлено в 2002 и опубликовано ими в 2006.

Полутранзитивный граф — это граф, который и вершинно-транзитивен, и рёберно-транзитивен, но не симметричен. Другими словами, граф полутранзитивен, если его группа автоморфизмов действует транзитивно как на вершины, так и на рёбра, но не на упорядоченные пары связанных вершин.

Теорема де Брёйна — Эрдёша — классическая теорема теории графов доказанная Палом Эрдёшем и Николаасом де Брёйном.

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

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

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

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

Подробнее: Циркулянтный граф

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

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

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

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

Подробнее: Совершенный граф

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

Граф C является накрывающим графом другого графа G, если имеется накрывающее отображение из множества вершин C в множество вершин G. Накрывающее отображение f является сюръекцией и локальным изоморфизмом — окрестность вершины v в C отображается биективно в окрестность f(v) в G.

В теории графов рёберным графом L(G) неориентированного графа G называется граф L(G), представляющий соседство рёбер графа G.

Подробнее: Рёберный граф

Симметричный граф (или транзитивный относительно дуг граф) — граф G, для любых двух пар смежных вершин которого u1—v1 и u2—v2 имеется автоморфизм...

Однозначно раскрашиваемый граф — это k-цветный граф, допускающий только одну (правильную) k-раскраску (с точностью до перестановки цветов).

Фактор-критический граф (или почти сочетаемый граф .) — это граф с n вершинами, в котором каждый подграф с n − 1 вершинами имеет совершенное паросочетание. (Совершенное паросочетание в графе — это подмножество рёбер со свойством, что каждая из вершин графа является конечной вершиной в точности одного ребра из подмножества.)

Кубический граф — граф, в котором все вершины имеют степень три. Другими словами, кубический граф является 3-регулярным. Кубические графы называются также тривалентными.

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

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

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

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

Теоремы об изоморфизме в алгебре — ряд теорем, связывающих понятия фактора, гомоморфизма и вложенного объекта. Утверждением теорем является изоморфизм некоторой пары групп, колец, модулей, линейных пространств, алгебр Ли или прочих алгебраических структур (в зависимости от области применения). Обычно насчитывают три теоремы об изоморфизме, называемые Первой (также основная теорема о гомоморфизме), Второй и Третьей. Хотя подобные теоремы достаточно легко следуют из определения фактора и честь их открытия...

Бабочка имеет диаметр 2 и обхват 3, радиус 1, хроматическое число 3, хроматический индекс 4 и является как эйлеровым, так и графом единичных расстояний. Граф является вершинно 1-связным графом и рёберно 2-связным.

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

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

Подробнее: Выпуклый подграф

В теории графов рёберно-транзитивным графом называется граф G такой, что для любых двух рёбер e1 и e2 графа G, существует автоморфизм графа G, который отображает e1 в e2.

Подробнее: Рёберно-транзитивный граф

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

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

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

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

В теории графов неориентированный граф H называется минором графа G, если H может быть образован из G удалением рёбер и вершин и стягиванием рёбер.

Подробнее: Минор графа

Граф дружеских отношений (или граф датской мельницы, или n-лопастной вентилятор) Fn — это планарный неориентированный граф с 2n+1 вершинами и 3n рёбрами.

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

Универсальный граф — это бесконечный граф, содержащий любой конечный (или не более чем счётный) граф в качестве порождённого подграфа. Универсальный граф этого типа первым построил Р. Радо и этот граф теперь называется графом Радо или случайным графом. Более свежие работы фокусируются на универсальных графах для семейства графов F. То есть бесконечный граф, принадлежащий F, содержащий все конечные графы семейства F. Например, графы Хэнсона являются универсальными в этом смысле для графов без i-клик...

В теории графов outerplanar graph — это граф, допускающий планарную диаграмму, в которой все вершины принадлежат внешней грани.

Подробнее: Внешнепланарный граф

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

Связный граф — граф, содержащий ровно одну компоненту связности. Это означает, что между любой парой вершин этого графа существует как минимум один путь. Другими словами, нет изолированной вершины ( такой, которая не имеет соответствующих ей рёбер (называется "ребра, инцидентные вершине 1" (или 2) ).

В теории графов графом гиперкуба Qn называется регулярный граф с 2n вершинами, 2n−1n рёбрами и n рёбрами, сходящимися в одной вершине. Его можно получить как одномерный скелет геометрического гиперкуба. Например, Q3 — это граф, образованный 8 вершинами и 12 рёбрами трёхмерного куба. Граф можно получить другим образом, отталкиваясь от семейства подмножеств множества с n элементами путём использования в качестве вершин все подмножества и соединением двух вершин ребром, если соответствующие множества...

Подробнее: Граф гиперкуба

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

Подробнее: Ациклическая раскраска графа

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