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

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

Дата: 17-12-2020, 07:02 » Раздел: Статьи  » 

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

Определение

Граф C {displaystyle C} является ядром, если любой гомоморфизм f : C → C {displaystyle f:C o C} является изоморфизмом, то есть, это биекция вершин C {displaystyle C} .

Ядро графа G {displaystyle G} — это граф C {displaystyle C} , такой что

  • существует гомоморфизм из G {displaystyle G} в C {displaystyle C}
  • существует гомоморфизм из C {displaystyle C} в G {displaystyle G}
  • с этими свойствами граф C {displaystyle C} минимален.
  • Говорят, что два графа гомоморфно эквивалентны, если они обладают изоморфными ядрами.

    Примеры

    • Любой полный граф является ядром.
    • Цикл нечётного порядка является своим же ядром.
    • Любые два цикла чётного порядка, и более обще, любые два двудольных графа гомоморфно эквивалентны. Ядром любого такого графа является полный граф K2 с двумя вершинами.

    Свойства

    Любой граф имеет единственное (с точностью до изоморфизма) ядро. Ядро графа G всегда является порождённым подграфом графа G. Если G → H {displaystyle G o H} и H → G {displaystyle H o G} , то графы G {displaystyle G} и H {displaystyle H} обязательно гомоморфно эквивалентны.

    Вычислительная сложность

    Задача проверки, имеет ли граф гомоморфизм в собственный подграф, является NP-полной, и ко-NP-полной задачей является проверка, является ли граф своим собственным ядром (то есть, что не существует гомоморфизмов в собственные подграфы).


    (голосов:0)

    Пожожие новости
    Комментарии

    Ваше Имя:   Ваш E-Mail: