Ամփոփում:

Դիցուք G-ն կապակցված գրաֆ է X գագաթների և U կողերի բարձրությամբ: Յուրաքանչյուր փոխմիարժեք φ համապատասխանություն, որ գագաթների X բազմությունը արտապատկերում է {1, 2, . . . , |X|} բազմության վրա, կոչվում է G գրաֆի համարակալում: �� φ (��) = max φ (��) − φ (��) թիվը, որտեղ մաքսիմումը վերցվում է ըստ գրաֆի բոլոր կողերի, սահմանվում է որպես φ համարակալման բարձրություն: G գրաֆի բարձրությունը սահմանվում է որպես B(G) = min�� φ (��), որտեղ մինիմումը վերցվում է ըստ գրաֆի բոլոր համարակալումների: Ինտերվալ գրաֆը սահմանվում է որպես թվային առանցքի վրա տրված ինտերվալների ինչ-որ ընտանիքի հատումների գրաֆ: Աշխատանքում բերվում է ինտերվալ գրաֆների բարձրությունը գտնող պոլինոմիալ բարդությամբ ալգորիթմ: Ալգորիթմն ունի O(nΔ2log(Δ)) բարդություն, որտեղ n-ը գրաֆի գագաթների քանակն է, իսկ Δ-ն՝ գագաթների մեծագույն աստիճանը:
; Пусть G=(X, U) – граф со множеством вершин X и ребер U. Каждое взаимно-однозначное отображение φ:X→{1,2….|X|} назовем его нумерацией. При этом число | φ (��)− φ (��)| назовем длиной ребра (x,y), а числа Bφ (G)=max(��,��)∈U| φ (��)− φ (��)| и B(G)=min B φ (G), где минимум берется по всевозможным нумерациям графа G, соответственно - высотой нумерации φ и графа G. Граф интервалов определяется как граф пересечений семейства интервалов данных на числовой прямой. В настоящей работе приводится алгоритм полиномиальной сложности для нахождения высоты произвольного графа интервалов. Алгоритм имеет сложность O(nΔ2log(Δ)), где n – количество вершин, а Δ – максимальная степень вершин графа.

Նույնականացուցիչ:

oai:noad.sci.am:136066