Существуют ли «графические» алгебры, которые могут описать «форму» графов?

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

Мой вопрос: существуют ли «графические» алгебры, которые могут описать «форму» графов?

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

ОБНОВИТЬ:

Мой вопрос, вероятно, очень узкий и не сразу отвечает "да", поэтому, если модераторы не возражают, я расширю его, спросив:

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

мотивация

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

Практический пример, где такая система будет полезна

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

Да, я знаю, что в этой последней части я волочусь от руки ... Если бы я не был, хотя, возможно, я бы сам начал создавать такую ​​систему!

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

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

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

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

При доказательстве теоремы о сильном совершенном графе использовалось несколько иное разложение. Ключевой результат: для каждого графа Берге$G$, или $G$ является основным, или один из $G, \overline{G}$ допускает правильное 2-соединение, или $G$ допускает сбалансированный перекос перегородки.

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

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

Хороший подход был представлен на ICFP в прошлом году: «Алгебраические графы с классом (функциональная жемчужина)» , автор Андрей Мохов.

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