Ирмэгийн холбоос / Оройн холбоос¶
Тодорхойлолт¶
$n$ орой, $m$ ирмэгтэй чиглэлгүй граф $G$ өгөгдсөн. Ирмэгийн холбоос ба оройн холбоос хоёул графыг тодорхойлдог үзүүлэлт юм.
Ирмэгийн холбоос¶
Граф $G$-ийн ирмэгийн холбоос $\lambda$ гэдэг нь граф $G$-г холбоост биш болгохын тулд устгах шаардлагатай ирмэгийн хамгийн бага тоо юм.
Жишээ нь аль хэдийн холбоост биш граф $0$ ирмэгийн холбоостой, дор хаяж нэг гүүртэй холбоост граф $1$ ирмэгийн холбоостой, гүүргүй холбоост граф дор хаяж $2$ ирмэгийн холбоостой байна.
Хэрэв граф $G$-ээс $S$ дахь бүх ирмэгийг хассаны дараа $s$ ба $t$ оройнууд өөр өөр холбоост компонентод орвол бид ирмэгүүдийн олонлог $S$ нь $s$ ба $t$ оройнуудыг тусгаарлана гэж хэлнэ.
Графын ирмэгийн холбоос нь боломжит бүх хос $(s, t)$-ийн дундаас авсан хоёр орой $s$ ба $t$-г тусгаарлах ийм олонлогийн хамгийн бага хэмжээтэй тэнцүү болох нь тодорхой.
Оройн холбоос¶
Граф $G$-ийн оройн холбоос $\kappa$ гэдэг нь граф $G$-г холбоост биш болгохын тулд устгах шаардлагатай оройн хамгийн бага тоо юм.
Жишээ нь аль хэдийн холбоост биш граф $0$ оройн холбоостой, зангилаа цэгтэй холбоост граф $1$ оройн холбоостой байна. Бид бүрэн граф $n-1$ оройн холбоостой гэж тодорхойлно. Бусад бүх графын хувьд оройн холбоос $n-2$-оос хэтрэхгүй, учир нь та ирмэгээр холбогдоогүй оройн хосыг олж, бусад $n-2$ оройг бүгдийг нь хасаж болно.
Хэрэв граф $G$-ээс $T$ дахь бүх оройг хассаны дараа оройнууд өөр өөр холбоост компонентод орвол бид оройнуудын олонлог $T$ нь $s$ ба $t$ оройнуудыг тусгаарлана гэж хэлнэ.
Графын оройн холбоос нь боломжит бүх хос $(s, t)$-ийн дундаас авсан хоёр орой $s$ ба $t$-г тусгаарлах ийм олонлогийн хамгийн бага хэмжээтэй тэнцүү болох нь тодорхой.
Шинж чанарууд¶
Уитнигийн тэнцэтгэл бишүүд¶
Уитнигийн тэнцэтгэл бишүүд (1932) нь ирмэгийн холбоос $\lambda$, оройн холбоос $\kappa$, ба граф дахь дурын оройн хамгийн бага зэрэг $\delta$-ийн хоорондох хамаарлыг өгнө:
Зөнгөөрөө бол хэрэв бидэнд графыг холбоост биш болгодог $\lambda$ хэмжээтэй ирмэгүүдийн олонлог байвал бид тус бүрийн нэг үзүүрийн цэгийг сонгож, мөн графыг холбоост биш болгодог оройнуудын олонлогийг үүсгэж болно. Мөн энэ олонлог $\le \lambda$ хэмжээтэй.
Хэрэв бид хамгийн бага зэрэг $\delta$-тэй оройг сонгоод түүнтэй холбогдсон бүх ирмэгийг хасвал бид мөн холбоост биш графтай үлдэнэ. Тиймээс хоёр дахь тэнцэтгэл биш $\lambda \le \delta$.
Уитнигийн тэнцэтгэл бишүүдийг сайжруулах боломжгүй болохыг тэмдэглэх нь сонирхолтой: өөрөөр хэлбэл энэ тэнцэтгэл бишийг хангах дурын гурван тооны хувьд дор хаяж нэг харгалзах граф оршино. Ийм нэг графыг дараах байдлаар байгуулж болно: Граф $2(\delta + 1)$ оройноос бүрдэх ба эхний $\delta + 1$ орой клик үүсгэнэ (оройн бүх хос ирмэгээр холбогдсон), хоёр дахь $\delta + 1$ орой хоёр дахь клик үүсгэнэ. Түүнчлэн бид хоёр кликийг $\lambda$ ирмэгээр, эхний кликт $\lambda$ өөр орой, хоёр дахь кликт зөвхөн $\kappa$ орой ашиглахаар холбоно. Үүссэн граф гурван үзүүлэлттэй байх болно.
Форд-Фалкерсоны теорем¶
Форд-Фалкерсоны теорем нь хоёр оройг холбох ирмэгээрээ огтлолцолгүй замуудын хамгийн их тоо нь эдгээр оройг тусгаарлах ирмэгийн хамгийн бага тоотой тэнцүү болохыг илэрхийлнэ.
Утгуудыг тооцоолох¶
Хамгийн их урсгал ашиглан ирмэгийн холбоосыг олох¶
Энэ арга Форд-Фалкерсоны теорем дээр суурилна.
Бид оройн бүх хос $(s, t)$-г тойрч, хос бүрийн хооронд тэдгээрийн хоорондох огтлолцолгүй замуудын хамгийн их тоог олно. Энэ утгыг хамгийн их урсгалын алгоритм ашиглан олж болно: бид $s$-г эх, $t$-г цорго болгон ашиглаж, ирмэг бүрд $1$ багтаамж оноодог. Тэгвэл хамгийн их урсгал нь огтлолцолгүй замуудын тоо болно.
Эдмондс-Карп ашиглах алгоритмын complexity нь $O(V^2 V E^2) = O(V^3 E^2)$. Гэвч энэ нь нуугдмал тогтмол агуулж байгааг тэмдэглэх хэрэгтэй, учир нь хамгийн их урсгалын алгоритм бүх эх ба цоргоны хувьд удаан ажиллах граф үүсгэх нь практикт боломжгүй. Ялангуяа санамсаргүй графуудын хувьд алгоритм нэлээд хурдан ажиллана.
Ирмэгийн холбоосын тусгай алгоритм¶
Ирмэгийн холбоосыг олох даалгавар нь глобал хамгийн бага огтлолыг олох даалгавартай тэнцүү.
Энэ даалгаварт зориулж тусгай алгоритмууд боловсруулсан. Тэдгээрийн нэг нь $O(V^3)$ эсвэл $O(V E + V^2 \log V)$ хугацаанд ажилладаг Штөр-Вагнерийн алгоритм юм.
Оройн холбоос¶
Дахин бид оройн бүх хос $s$ ба $t$-г тойрч, хос бүрийн хувьд $s$ ба $t$-г тусгаарлах оройн хамгийн бага тоог олно.
Үүнийг хийснээр бид өмнөх хэсгүүдэд тайлбарласан ижил хамгийн их урсгалын аргыг хэрэглэж болно.
Бид $x \neq s$ ба $x \neq t$ байх орой $x$ бүрийг $x_1$ ба $x_2$ гэсэн хоёр орой болгон хуваана. Бид эдгээр оройг $1$ багтаамжтай чиглэлтэй ирмэг $(x_1, x_2)$-ээр холбож, бүх ирмэг $(u, v)$-г $(u_2, v_1)$ ба $(v_2, u_1)$ гэсэн хоёр чиглэлтэй ирмэгээр, хоёуланг нь 1 багтаамжтайгаар солино. Тэгвэл байгуулалтаараа хамгийн их урсгалын утга $s$ ба $t$-г тусгаарлахад шаардагдах оройн хамгийн бага тоотой тэнцүү байх болно.
Энэ арга ирмэгийн холбоосыг олох урсгалын аргатай ижил complexity-тэй.