Шошготой графыг тоолох¶

Шошготой граф¶

Граф дахь оройн тоо $n$ байг. Бид $n$ оройтой шошготой графын тоо $G_n$-г тооцоолох ёстой (шошготой гэдэг нь оройнуудыг $1$-ээс $n$ хүртэлх тоогоор тэмдэглэсэн гэсэн үг). Графын ирмэгүүдийг чиглэлгүй гэж үзэх ба гогцоо, давхар ирмэгийг хориглоно.

Бид графын бүх боломжит ирмэгийн олонлогийг авч үзнэ. Ирмэг $(i, j)$ бүрийн хувьд бид $i < j$ гэж үзэж болно (учир нь граф чиглэлгүй, гогцоо байхгүй). Тиймээс бүх ирмэгийн олонлог $\binom{n}{2}$ буюу $\frac{n(n-1)}{2}$ хүчин чадалтай.

Дурын шошготой граф нь ирмэгүүдээрээ цор ганцаар тодорхойлогддог тул $n$ оройтой шошготой графын тоо нь:

$$G_n = 2^{\frac{n(n-1)}{2}}$$

Холбоост шошготой граф¶

Энд бид граф холбоост байх ёстой гэсэн нэмэлт хязгаарлалт тавина.

$n$ оройтой холбоост графын шаардлагатай тоог $C_n$ гэж тэмдэглэе.

Бид эхлээд хэдэн холбоосгүй граф байгааг авч үзнэ. Тэгвэл холбоост графын тоо нь $G_n$-ээс холбоосгүй графын тоог хассантай тэнцүү болно. Түүнчлэн бид холбоосгүй, үндэстэй графын тоог тоолно. Үндэстэй граф гэдэг нь бид нэг оройг үндэс гэж шошголон онцолсон граф юм. $n$ шошготой оройтой графыг үндэслэх $n$ боломж байгаа нь ойлгомжтой тул холбоосгүй графын тоог олохын тулд эцэст нь холбоосгүй үндэстэй графын тоог $n$-д хуваах хэрэгтэй болно.

Үндэс орой нь $1, \dots n-1$ хэмжээтэй холбоост компонентэд гарч ирнэ. Үндэс орой нь $k$ оройтой холбоост компонентэд байх $k \binom{n}{k} C_k G_{n-k}$ граф байна (компонентэд $k$ орой сонгох $\binom{n}{k}$ арга байх ба тэдгээрийг $C_k$ аргын нэгээр холбоно, үндэс орой нь $k$ оройн аль нэг байж болох ба үлдсэн $n-k$ орой нь дурын байдлаар холбогдсон/холбоосгүй байж болох ба энэ нь $G_{n-k}$ хүчин зүйлийг өгнө). Тиймээс $n$ оройтой холбоосгүй графын тоо нь:

$$\frac{1}{n} \sum_{k=1}^{n-1} k \binom{n}{k} C_k G_{n-k}$$

Эцэст нь холбоост графын тоо нь:

$$C_n = G_n - \frac{1}{n} \sum_{k=1}^{n-1} k \binom{n}{k} C_k G_{n-k}$$

$k$ холбоост компоненттэй шошготой граф¶

Өмнөх хэсгийн томьёон дээр үндэслэн бид $n$ оройтой, $k$ холбоост компоненттэй шошготой графын тоог хэрхэн тоолохыг сурна.

Энэ тоог динамик программчлал ашиглан тооцоолж болно. Бид $i \le n$ ба $j \le k$ бүрийн хувьд $D[i][j]$ буюу $i$ оройтой, $j$ компоненттэй шошготой графын тоог тооцоолно.

Өмнөх утгуудыг аль хэдийн мэддэг бол дараагийн элемент $D[n][k]$-г хэрхэн тооцоолохыг авч үзье. Бид түгээмэл аргыг ашиглаж, сүүлийн оройг (индекс $n$) авна. Энэ орой ямар нэг компонентэд харьяалагдана. Энэ компонентын хэмжээг $s$ гэвэл ийм оройн олонлог сонгох $\binom{n-1}{s-1}$ арга, тэдгээрийг холбох $C_s$ арга байна. Энэ компонентыг графаас хассаны дараа бидэнд $k-1$ холбоост компоненттэй $n-s$ орой үлдэнэ. Тиймээс бид дараах рекуррент хамаарлыг олж авна:

$$D[n][k] = \sum_{s=1}^{n} \binom{n-1}{s-1} C_s D[n-s][k-1]$$