Кіріспе
Графтың шеттерін жиырыстыру арқылы жасалған ең үлкен толық графтың мөлшері
Графтар теориясында, бағытталмаған G графигінің Хадвигер саны – G графигінің шеттерін жиырыстыру арқылы алынған ең үлкен толық графтың мөлшері болып табылады. Басқаша айтқанда, Хадвигер саны h(G) – G графигінің миноры болатын толық графтың ең үлкен саны n, яғни G графигінен шеттерді жиырыстыру және төбелер мен шеттерді жою арқылы алынған кіші граф. Хадвигер саны G графигінің жиырылу тобының саны немесе G графигінің гомоморфизм дәрежесі деп те аталады. Ол 1943 жылы Хадвигер болжамымен бірге енгізген Хуго Хадвигердің есімімен аталған, онда Хадвигер саны G графигінің түстік санынан кем болмайды деп айтылады.
Equivalently, the Hadwiger number h(G) is the largest number n for which the complete graph is a minor of G, a smaller graph obtained from G by edge contractions and vertex and edge deletions. The Hadwiger number is also known as the contraction clique number of G or the homomorphism degree of G. It is named after Hugo Hadwiger, who introduced it in 1943 in conjunction with the Hadwiger conjecture, which states that the Hadwiger number is always at least as large as the chromatic number of G.
Хадвигер саны төрттен аспайтын графтар сипатталған. Хадвигер санына шектеу қойылған графтар сиректеу болады және олардың түстік саны кішкентай. Графтың Хадвигер санын анықтау NP-қиын мәселе, бірақ параметрлік тұрақтылықпен шешіледі.
Кіші Хадвигер саны бар графиктер
G графигінің Гадвигер саны ең көп дегенде екі болса, ол орман болады, өйткені үш төбелі толық минорды G-дегі циклды қысқарту арқылы ғана құруға болады.
График Гадвигер саны ең көп дегенде үш болса және тек қана оның ағаш ені ең көп дегенде екі болса, бұл оның екі байланысты компоненттерінің әрқайсысы тізбекті-параллель граф болса ғана дұрыс. Вагнер теоремасы, жазық графтарды олардың тыйым салынған минорлары арқылы сипаттайды, жазық графтардың Гадвигер саны ең көп дегенде төрт екенін көрсетеді. Осы теореманы дәлелдеген мақалада, Гадвигер саны ең көп дегенде төрт болатын графтар да дәлірек сипатталды: олар жазық графтарды сегіз төбелі Вагнер графигімен кликалық қосынды операциялары арқылы біріктіру арқылы құрылатын графтар. Гадвигер саны ең көп дегенде бес болатын графтарға төбелік графтар және байланыссыз ендірілетін графтар жатады, олардың екеуінде де тыйым салынған минорлардың арасында толық граф бар.
Қанықсыздық
n төбесі және k Хадвигер саны бар кез келген графтың O(nk√log k) жиегі болады. Бұл шектеу нақты: кез келген k үшін, k Хадвигер саны бар және Ω(nk√log k) жиегі бар графтар бар. Егер G графының Хадвигер саны k болса, онда оның барлық ішкі графтарының Хадвигер саны да k-дан аспайды, сондықтан G-нің дегенерациясы O(k√log k) болуы керек. Демек, шектелген Хадвигер саны бар графтар сиреп жатқан графтар болып табылады.
Түстеу
Хадвигерлік болжам Хадвигерлік санның әрқашан G графигінің хроматикалық санынан кем болмауын айтады. Яғни, Хадвигерлік саны k болатын әрбір графты ең көп дегенде k түспен бояуға болады. 1=k = 4 жағдайы (Вагнердің осы Хадвигерлік саны бар графтарды сипаттауы бойынша) жазық графтарды түспен бояу туралы төрт түс теоремасына эквивалентті, және болжам k ≤ 5 үшін де дәлелденген, бірақ k-ның үлкен мәндері үшін дәлелденбеген күйде қалады. Төмен дегенерациясы болғандықтан, Хадвигерлік саны ең көп дегенде k-ға тең графтарды ашкөз бояу алгоритмімен O(k√log k) түс қолданып бояуға болады.
Because of their low degeneracy, the graphs with Hadwiger number at most k can be colored by a greedy coloring algorithm using O(k \sqrt{ \log k}) colors.
Есептеу күрделілігі
Берілген графтың Хадвигерлік санының кем дегенде берілген k мәніне тең немесе одан жоғары екенін тексеру NP-толық, содан Хадвигерлік санды анықтау NP-қиын екендігі шығады. Дегенмен, бұл мәселе тұрақты параметрмен шешіледі: графтың өлшемдеріне ғана полиномиялық түрде, бірақ h(G)-ға экспоненциалды түрде тәуелді уақытта ең үлкен кликалық кіші графты табуға арналған алгоритм бар. Сонымен қатар, полиномиалдық уақыт алгоритмдері Хадвигерлік санды ең жақсы полиномиалдық уақытпен жуықтаудан (P ≠ NP болған жағдайда) ең үлкен толық субграфтың өлшеміне қарағанда әлдеқайда дәлірек бағалай алады.
Қарым-қатынас ұғымдары
G графигінің ахроматикалық саны – G-дегі тәуелсіз жиындардың отбасын қысқарту арқылы құрастырылатын ең үлкен кликаның өлшемі. Шегі жоқ графиктердегі санауға келмейтін клика кішілері паналар арқылы сипатталуы мүмкін, олар белгілі бір қуғын-құтылу ойындары үшін қашу стратегияларын формалдайды: егер Хадвигер саны санауға келмейтін болса, онда ол графтың ең үлкен тәртібіндегі панаға тең болады. Хадвигер саны k болатын әрбір графтың ең көп дегенде кликалары (толық қоссалған кішграфтар) болады. Ол граф параметрлерінің класын анықтайды, оны S функциялары деп атайды, және Хадвигер саны олардың ішінде. Бұл функциялар графтардан бүтін сандарға өтуі керек, шеттері жоқ графтар үшін нөл болуы, кішілеу бойынша монотонды болуы, барлық бұрынғы төбелерімен іргелес жаңа төбе қосылғанда біреуге артуы, және екі кішграфтың арасындағы клика бөлігішіндегі екі мәннен үлкенін алуы керек. Мұндай функциялардың барлық жиынтығы элемент бойынша ең кіші және ең үлкен мәнді табу операциялары бойынша толық тор құрайды. Бұл тордың ең төменгі элементі – Хадвигер саны, ал ең жоғарғы элементі – ағаш ені.
Uncountable clique minors in infinite graphs may be characterized in terms of havens, which formalize the evasion strategies for certain pursuit–evasion games: if the Hadwiger number is uncountable, then it equals the largest order of a haven in the graph. Every graph with Hadwiger number k has at most cliques (complete subgraphs). defines a class of graph parameters that he calls S functions, which include the Hadwiger number. These functions from graphs to integers are required to be zero on graphs with no edges, to be minor monotone, to increase by one when a new vertex is added that is adjacent to all previous vertices, and to take the larger value from the two subgraphs on either side of a clique separator. The set of all such functions forms a complete lattice under the operations of elementwise minimization and maximization. The bottom element in this lattice is the Hadwiger number, and the top element is the treewidth.