Партнерка на США и Канаду по недвижимости, выплаты в крипто

  • 30% recurring commission
  • Выплаты в USDT
  • Вывод каждую неделю
  • Комиссия до 5 лет за каждого referral

ИДЕНТИФИКАТОРЫ ВЕРШИН ПОМЕЧЕННЫХ ГРАФОВ

,

Институт прикладной математики и механик НАНУ, Украина, Донецк

Рассматриваются условия существования конечных подмножеств языков вершин, отделяющих порождающую их вершину от всех других вершин помеченного графа.

Помеченным графом назовем четверку , где – множество вершин, , , – множество меток вершин, , – сюръективная функция разметки. Множество называется открытой окрестностью вершины , а множество – ее замкнутой окрестностью. Граф назовем D-графом (SD-графом), если для любой вершины и любых вершин из следует . Последовательность меток вершин , соответствующую пути в графе , назовем словом. Пусть и , тогда обозначает множество вершин таких, что существует путь из в с меткой . Пусть , , тогда и не определено, если . Обозначим через множество всех слов, порожденных вершиной . Две вершины назовем неотличимыми и будем писать , если . Конечное множество слов назовем идентификатором вершины , если тогда и только тогда, когда . назовем кратностью, а – высотой . Ясно, что , где и . Идентификатор назовем позитивным, если и негативным, если .

Теорема 1. Равносильны следующие утверждения: (1) Существует идентификатор вершины . (2) Существует идентификатор вершины высоты не больше и кратности не больше . (3) .

Следствие. Для любой вершины приведенного графа существует идентификатор высоты не больше и кратности не больше , где , .

Теорема 2. (1) Простой позитивный идентификатор вершины существует тогда и только тогда, когда . (2) Простой негативный идентификатор вершины существует тогда и только тогда, когда .

Для SD-графов справедливы следующие утверждения

Теорема 3. Пусть – позитивный идентификатор вершины и «, тогда – позитивный идентификатор вершины .

Теорема 4. Кратный позитивный идентификатор вершины приведенного максимального SD-графа существует тогда и только тогда, когда существует простой позитивный идентификатор этой вершины.

Следствие. Высота простого позитивного идентификатора вершины приведенного максимального SD-графа равна .