Підтримка
www.wikidata.uk-ua.nina.az
Invaria nt Kolen de Verdyera harakteristika grafa m G displaystyle mu G viznachena dlya bud yakogo grafa G displaystyle G yaku vviv fr v procesi doslidzhennya kratnosti drugogo vlasnogo znachennya deyakih operatoriv Shredingera ViznachennyaNehaj G V E displaystyle G V E prostij bez petel i kratnih reber aciklichnij graf Bez vtrati zagalnosti poimenuyemo mnozhinu vershin u takij sposib V 1 n displaystyle V 1 dots n Todi m G displaystyle mu G najbilshij en bud yakoyi takoyi simetrichnoyi matrici M M i j R n displaystyle M M i j in mathbb R n sho M1 dlya bud yakih i j displaystyle i j de i j displaystyle i neq j M i j lt 0 displaystyle M i j lt 0 yaksho i j E displaystyle i j in E i M i j 0 displaystyle M i j 0 yaksho i j E displaystyle i j notin E M2 M displaystyle M maye rivno odne vid yemne vlasne znachennya kratnosti 1 displaystyle 1 M3 ne isnuye takoyi nenulovoyi matrici X X i j R n displaystyle X X i j in mathbb R n sho M X 0 displaystyle MX 0 i sho X i j 0 displaystyle X i j 0 shorazu koli i j displaystyle i j abo M i j 0 displaystyle M i j neq 0 Klasifikaciya vidomih grup grafivZ tochki zoru invarianta Kolen de Verdyera deyaki dobre vidomi simejstva grafiv mayut harakterni osoblivosti m K 1 0 displaystyle mu K 1 0 m K n n 1 displaystyle mu K n n 1 m K n 1 displaystyle mu overline K n 1 pri n gt 1 displaystyle n gt 1 m 1 todi j lishe todi koli G ye linijnim lisom lisom u yakomu kozhen komponent ye shlyahom tobto incidentnist bud yakoyi vershini ne bilsha vid 2 m 2 todi j lishe todi koli G ye zovniplanarnim grafom usi vershini lezhat na odnij grani m 3 todi j lishe todi koli G ye planarnim grafom m 4 todi j lishe todi koli G ye nezachepleno vklada nim tobto ne isnuye dvoh cikliv u G dlya yakih pri vidobrazhenni na evklidiv prostir koeficiyent zacheplennya dorivnyuye nulyu Ci zh grupi grafiv proyavlyayut svoyi vidminni risi i pid chas analizu zv yazku mizh invariantom grafa i dopovnennyam cogo grafa Yaksho dopovnennya grafa z n vershinami ye linijnim lisom to m n 3 Yaksho dopovnennya grafa z n vershinami ye zovniplanarnim grafom to m n 4 Yaksho dopovnennya grafa z n vershinami ye planarnim grafom to m n 5 Minori grafivMinorom grafa G nazivayut graf H otrimanij z G poslidovnim vidalennyam vershin vidalennyam reber i stisnennyam reber Invariant Kolena de Verdyera monotonnij vidnosno operaciyi vzyattya minora v tomu sensi sho minoruvannya grafa ne mozhe zbilshiti jogo invarianta Yaksho H ye minorom G to m H m G displaystyle mu H leq mu G V teoremi Robertsona Sejmura dlya bud yakogo k isnuye H skinchenna mnozhina grafiv taka sho dlya bud yakogo grafa z invariantom ne bilshim vid k grafi z H ne mozhut buti minorami V roboti Colin de Verdiere 1990 perelicheno mnozhini takih nedopustimih minoriv dlya k 3 dlya k 4 mnozhina nedopustimih minoriv skladayetsya z semi grafiv simejstva Petersena za viznachennyam nezachepleno vkladenogo grafa yak grafa z m 4 i bez grafiv Petersena yak minoriv Zv yazok iz hromatichnim chislomKolen de Verdyer Colin de Verdiere 1990 pripustiv sho bud yakij graf z invariantom de Verdera m mozhna rozfarbuvati z vikoristannyam ne bolshe nizh m 1 koloriv Napriklad u linijnih lisiv komponenti yakih ye dvochastkovimi grafami invariant dorivnyuye 1 u zovniplanarnih grafiv invariant dorivnyuye 2 i yih mozhna rozfarbuvati troma kolorami u planarnih grafiv invariant 3 i yih mozhna rozfarbuvati chotirma kolorami Dlya grafiv z invariantom de Verdyera ne bilshe chotiroh pripushennya istinne voni vsi ye nezachepleno vkladanimi i toj fakt sho voni rozfarbovuyutsya p yatma kolorami ye naslidkom dovedennya gipotezi Hadvigera dlya grafiv bez minoriv tipu K6 u roboti Robertsona Sejmura ta Tomasa Robertson Seymour ta Thomas 1993 Inshi vlastivostiYaksho chislo peretiniv grafa dorivnyuye k to invariant de Verdyera dlya nogo bude ne bilshim nizh k 3 Napriklad grafi Kuratovskogo K5 i K3 3 mozhna zobraziti z odnim peretinom i invariant dlya nih bude ne bilshim vid chotiroh Primitki van der Holst Lovasz ta Schrijver 1999 Colin de Verdiere 1990 U praci Colin de Verdiere 1990 cej vipadok yavno ne rozglyanuto ale vin yavno viplivaye z rezultativ analizu grafiv yaki ne mayut minoriv vidu trikutnik i kleshnya Lovasz ta Schrijver 1998 Kotlov Lovasz ta Vempala 1997 Posilannya 1990 Sur un nouvel invariant des graphes et un critere de planarite 50 1 11 21 doi 10 1016 0095 8956 90 90093 F van der Holst Hein Lovasz Laszlo 1999 The Colin de Verdiere graph parameter Bolyai Soc Math Stud t 7 Budapest Janos Bolyai Math Soc s 29 85 arhiv originalu za 3 bereznya 2016 procitovano 20 sichnya 2022 Kotlov Andrew Lovasz Laszlo Vempala Santosh 1997 Combinatorica 17 4 483 521 doi 10 1007 BF01195002 arhiv originalu za 3 bereznya 2016 procitovano 20 sichnya 2022 Lovasz Laszlo 1998 A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs 126 5 1275 1285 doi 10 1090 S0002 9939 98 04244 0 1993 PDF 13 279 361 doi 10 1007 BF01202354 arhiv originalu PDF za 10 kvitnya 2009 procitovano 20 sichnya 2022
Топ