Показать меню

Граф Кауца

23.03.2021
33

Граф Кауца K M N + 1 {displaystyle K_{M}^{N+1}} — это ориентированный граф степени M {displaystyle M} и размерности N + 1 {displaystyle N+1} , который имеет ( M + 1 ) M N {displaystyle (M+1)M^{N}} вершин, помеченных всеми возможными строками s 0 ⋯ s N {displaystyle s_{0}cdots s_{N}} длины N + 1 {displaystyle N+1} , которые составлены из символов s i {displaystyle s_{i}} , выбранных из алфавита A {displaystyle A} , содержащего M + 1 {displaystyle M+1} различных символов с условием, что соседние символы не могут совпадать ( s i ≠ s i + 1 {displaystyle s_{i} eq s_{i+1}} ).

Граф Кауца K M N + 1 {displaystyle K_{M}^{N+1}} имеет ( M + 1 ) M N + 1 {displaystyle (M+1)M^{N+1}} рёбер

{ ( s 0 s 1 ⋯ s N , s 1 s 2 ⋯ s N s N + 1 ) | s i ∈ A s i ≠ s i + 1 } {displaystyle {(s_{0}s_{1}cdots s_{N},s_{1}s_{2}cdots s_{N}s_{N+1})|;s_{i}in A;s_{i} eq s_{i+1}},}

Естественно пометить каждое такое ребро K M N + 1 {displaystyle K_{M}^{N+1}} как s 0 s 1 ⋯ s N + 1 {displaystyle s_{0}s_{1}cdots s_{N+1}} , создавая один-к-одному соответствие между рёбрами графа Кауца K M N + 1 {displaystyle K_{M}^{N+1}} и вершинами графа Кауца K M N + 2 {displaystyle K_{M}^{N+2}} .

Графы Кауца тесно связаны с графами де Брёйна.

Свойства

  • Для фиксированной степени M {displaystyle M} и числа вершин V = ( M + 1 ) M N {displaystyle V=(M+1)M^{N}} граф Кауца имеет наименьший диаметр для любого ориентированного графа с V {displaystyle V} вершинами и степенью M {displaystyle M} .
  • Все графы Кауца имеют эйлеровы циклы. (Эйлеров цикл — это цикл, который посещает каждое ребро ровно раз — этот результат следует из того, что графы Кауца имеют полустепень захода равную полустепени исхода для каждого узла).
  • Все графы Кауца имеют гамильтонов цикл (Этот результат следует из соответствия, описанного выше между рёбрами графа Кауца K M N {displaystyle K_{M}^{N}} и вершинами графа Кауца K M N + 1 {displaystyle K_{M}^{N+1}} . Гамильтонов цикл на K M N + 1 {displaystyle K_{M}^{N+1}} задаётся эйлеровым циклом на K M N {displaystyle K_{M}^{N}} ).
  • Граф Кауца степени k {displaystyle k} имеет k {displaystyle k} непересекающихся пути из любого узла x {displaystyle x} в любой другой узел y {displaystyle y} .

В обработке данных

Граф Кауца использовался в качестве сетевой технологии для соединения процессоров в высокопроизводительных вычислениях и отказоустойчивых вычислениях, такие сети известны как сети Кауца.

Еще по этой теме:
Эйлеровы числа
05:09, 18 декабрь
Эйлеровы числа
Эйлеровы числа (или числа Эйлера) — целые числа E 0 , E 1
Нётерово пространство
01:20, 15 декабрь
Нётерово пространство
Нётерово пространство (по имени Эмми Нётер) — топологическое пространство X, удовлетворяющее условию обрыва убывающих цепей замкнутых подмножеств. То есть для каждой последовательности замкнутых
Существенно особая точка
14:44, 12 декабрь
Существенно особая точка
Изолированная особая точка z 0 {displaystyle z_{0}} функции f (
Граф Кэли
19:23, 10 декабрь
Граф Кэли
Граф Кэли — граф, который строится по группе с выделенной системой образующих. Назван в честь Артура Кэли. Определение Пусть дана дискретная группа G
Максимальный тор
12:52, 03 декабрь
Максимальный тор
Максимальный тор связной вещественной группы Ли G {displaystyle G} — связная компактная коммутативная подгруппа Ли T
Вариационный ряд
08:23, 03 декабрь
Вариационный ряд
Вариационный ряд (упорядоченная выборка) — последовательность X ( 1 ) ⩽
Комментарии:
Добавить комментарий
Ваше Имя:
Ваш E-Mail:
  • bowtiesmilelaughingblushsmileyrelaxedsmirk
    heart_eyeskissing_heartkissing_closed_eyesflushedrelievedsatisfiedgrin
    winkstuck_out_tongue_winking_eyestuck_out_tongue_closed_eyesgrinningkissingstuck_out_tonguesleeping
    worriedfrowninganguishedopen_mouthgrimacingconfusedhushed
    expressionlessunamusedsweat_smilesweatdisappointed_relievedwearypensive
    disappointedconfoundedfearfulcold_sweatperseverecrysob
    joyastonishedscreamtired_faceangryragetriumph
    sleepyyummasksunglassesdizzy_faceimpsmiling_imp
    neutral_faceno_mouthinnocent