K-шыңына байланысты график - K-vertex-connected graph

Байланысты график 4.

Жылы графтар теориясы, а қосылған график G деп айтылады к-текске қосылған (немесе к- байланысты) егер одан көп болса к төбелер және қалады байланысты кем болған сайын к шыңдар жойылды.

The шың-байланыс, немесе жай қосылым, графиктің ең үлкені к ол үшін график к-текске қосылған.

Анықтамалар

График (а-дан басқа) толық граф ) байланысқа ие к егер к - бұл шыңдардың ең кіші жиынының өлшемі, егер сіз оларды жойсаңыз, график ажыратылады.^[1] Толық графиктер анықтаманың осы нұсқасына кірмейді, өйткені оларды шыңдарды өшіру арқылы ажырату мүмкін емес. Толық график n шыңдардың байланысы бар n - 1, бірінші анықтамада айтылғандай.

Эквивалентті анықтама - кем дегенде екі төбесі бар график к- егер оның әр шыңы үшін табуға болатын болса, байланысты к шыңға тәуелсіз жолдар осы шыңдарды байланыстыру; қараңыз Менгер теоремасы (Diestel 2005, б. 55) Бұл анықтама бірдей жауап береді, n - 1, толық графиктің қосылымы үшін Қ_n.^[1]

1-ге байланысты график деп аталады байланысты; 2-ге байланысты график деп аталады қосарланған. 3 қосылған графикті үш байланыстырылған деп атайды.

Қолданбалар

Көпбұрышты комбинаторика

1-қаңқа кез келген к-өлшемді дөңес политоп құрайды к-текске қосылған график (Балинский теоремасы, Балинский 1961 ж ). Ішінара әңгіме ретінде, Штайниц теоремасы кез-келген 3 шыңға байланысты екенін айтады жазықтық график дөңес қаңқасын құрайды полиэдр.

Есептеудің күрделілігі

Кіріс графигінің шың-байланысы G көпмүшелік уақытта келесі тәсілмен есептеуге болады^[2] барлық мүмкін жұптарды қарастырыңыз ${displaystyle (s, t)}$ пайдалану арқылы ажыратылатын түйіндер Менгер теоремасы үшін минималды өлшемдегі сепараторды негіздеу ${displaystyle (s, t)}$ - бұл олардың арасындағы жұптық шыңға тәуелсіз жолдардың саны, әр шыңды екі есе көбейтіп, қосарланған шеттерден тәуелсіз жолдар санына дейін азайту үшін кірісті кодтайды және осындай жолдардың максималды санын есептеу арқылы максималды ағын арасындағы графикте ${displaystyle s}$ және ${displaystyle t}$ ағыны бар екенін ескере отырып, әр шетіне сыйымдылығы 1 ${displaystyle k}$ осы графикке сәйкес келеді интегралды ағын теоремасы, дейін ${displaystyle k}$ бастап жиектен тәуелсіз жолдар ${displaystyle s}$ дейін ${displaystyle t}$ .

Сондай-ақ қараңыз

Ескертулер

^ ^а ^б Шрайвер (2003 ж. 12 ақпан), Комбинаторлық оңтайландыру, Springer, ISBN 9783540443896
^ Алгоритмді жобалау бойынша нұсқаулық, б 506, және Есептеу дискретті математика: комбинаторика және Mathematica-мен график теориясы, б. 290-291

Әдебиеттер тізімі

Балинский, М. Л. (1961), «дөңес полиэдраның графикалық құрылымы туралы n-ғарыш», Тынық мұхит журналы, 11 (2): 431–434, дои:10.2140 / pjm.1961.11.431.
Диестель, Рейнхард (2005), Графикалық теория (3-ші басылым), Берлин, Нью-Йорк: Спрингер-Верлаг, ISBN 978-3-540-26183-4.

[Schrijver-1] а ^б Шрайвер (2003 ж. 12 ақпан), Комбинаторлық оңтайландыру, Springer, ISBN 9783540443896

[2] Алгоритмді жобалау бойынша нұсқаулық, б 506, және Есептеу дискретті математика: комбинаторика және Mathematica-мен график теориясы, б. 290-291

[1]

[2]