200
правок
Изменения
→Описание
:Пусть <tex>G</tex> {{---}} граф Майхилла.
:Построим автомат <tex>\mathcal{A}</tex> следующим образом:
:* Добавим вершину <tex>c_ii</tex> в <tex>G</tex> с ребрами от <tex>c_ii</tex> к каждой стартовой вершине <tex>G</tex>; отметим вершину <tex>c_ii</tex> как стартовое состояние.
:* Отметим конечные вершины как терминальные состояния.
:* Отметим каждое ребро результирующего ориентированного графа символом, стоящим в вершине, на которою оно указывает.
