АНАЛІЗ ВПЛИВУ АВТОМОРФІЗМУ ГРАФУ НА СХЕМИ НАПРАВЛЕНОГО ПЕРЕБОРУ

  • K. D. Karavaiev
  • V. A. Turchyna
Ключові слова: дискретна оптимізація, теорія розкладів, оптимальні упорядкування, метод гілок та меж, перерахування без ізоморфізму

Анотація

У статі досліджується залежність між наявністю автоморфізму у графі та ізоморфізмом його підграфів, отриманих шляхом видаленням з нього відкритих вершин. Запропоновано алгоритм для скорочення кількості розгалужень у методі гілок та меж для задачі паралельного упорядкування вершин орграфів. Показано, що результуюча множина містить всі неізоморфні підграфи, проте також може містити й ізоморфні.

Переглядів анотації: 48
Завантажень PDF: 55
Опубліковано
2022-01-11