Автоморфизм графа

От / / Оставьте комментарий

Автоморфизм графа Определение автоморфизма графа Автоморфизм графа — это отображение, сохраняющее связность ребер и вершин.  Композиция автоморфизмов образует группу автоморфизмов.  […]

Algebraic graph theory, Алгебраическая теория графов

Автоморфизм графа

  • Определение автоморфизма графа

    • Автоморфизм графа — это отображение, сохраняющее связность ребер и вершин. 
    • Композиция автоморфизмов образует группу автоморфизмов. 

  • Вычислительная сложность и проблема автоморфизма

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

  • Алгоритмы и программное обеспечение

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

  • Практическое применение

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

  • Отображение симметрии и семейства графов

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

Полный текст статьи:

Автоморфизм графа — Википедия

Похожие статьи:

  1. Внутренний автоморфизм Внутренний автоморфизм Внутренний автоморфизм — автоморфизм группы, кольца или алгебры, заданный действием сопряжения фиксированного элемента.  Внутренние...
  2. Обход графа Обход графика Основы обхода графа Обход графа включает проверку и обновление каждой вершины в графе.  Обходы...
  3. Группа внешних автоморфизмов Группа внешних автоморфизмов Определение внешней группы автоморфизмов Внешняя группа автоморфизмов — это группа автоморфизмов, за исключением...
  4. Автоморфизм Автоморфизм Автоморфизм — преобразование, сохраняющее структуру объекта.  В математике автоморфизмы играют важную роль в теории Галуа...
  5. Анализ решений по множеству критериев Многокритериальный анализ принятия решений Определение и важность многокритериального принятия решений MCDM — это процесс выбора оптимального...
  6. Проблема изоморфизма графов Проблема изоморфизма графов Определение и сложность изоморфизма графов Изоморфизм графов — это проблема определения, являются ли...
  7. Встраивание графов Встраивание графа Определение и свойства вложения графа Вложение графа G на поверхности Σ — это представление...
  8. Альтернативные условия для бесплатного программного обеспечения Альтернативные условия для свободного программного обеспечения Определение и использование терминов «Свободное программное обеспечение» (FSF) и «программное...
  9. Связность (теория графов) Связность (теория графов) Определение связности в теории графов Связность — это свойство графа, при котором все...
  10. Переписывание графа Переписывание графиков Основы переписывания графов Переписывание графов — это процесс замены частей графа, основанный на правилах. ...
  11. Граф минор Второстепенный график Определение миноров графа Минор графа — это подграф, который является подграфом исходного графа и...
  12. Канонизация графа Канонизация графа Канонизация графов — задача нахождения канонической формы графа G.  Каноническая форма — изоморфный граф...
  13. Свойство графа Свойство графика Свойства графа — это свойства, сохраняемые при всех возможных изоморфизмах графа.  Инварианты графа —...
  14. Раскраска графа Раскрашивание графика Определение и свойства хроматического числа Хроматическое число графа — это минимальное количество цветов, необходимых...

Оставьте комментарий

Прокрутить вверх