Графын 2 бодлого

by Ганбат, posted in Нийтлэлүүд

Бодлого 1. 2n+1 хүнтэй нийгэмлэгт аль ч n хүний хувьд эдгээр n хүнийг бүгдийг таньдаг өөр нэг хүн нийгэмлэгээс олддог бол бүх хүнийг таньдаг нэг хүн олдоно гэж батал.

Бодолт 1. Эхлээд бид n+1 хүнтэй бүлгийг (бүлгийн аль ч хоёр хүн танилууд) доорхи аргаар байгуулж чадна. Эхлээд танил 2 хүн авч үзвэл энэ 2 хүнийг таньдаг 3 дахь хүн оршин байна. Дараа нь дээрхи 3 хүнийг 3 ууланг нь таньдаг нэг хүн оршин байна. Гэхмэт явсаар бүгд бие биеэ таньдаг n хүнтэй болно. Эдгээр n хүнтэй бүгдтэй нь танил өөр нэг хүн оршин байна. Игнээд n+1 хүнтэй бүлэг байгуулагдлаа. Үүнээс олон хүнтэй бүлэг оршино гэж бид хэлж чадахгүй. Одоо энэ n+1 хүнээс гаднах n хүнийг авч үзэхэд эдгээр хүмүүстэй танил хүн бүлэг дотроос олдоно. Тэр олдож байгаа хүн бүх хүнийг танидаг болж батлагдав.

Бодлого 2. Нийгэмлэгийн аль ч хоёр хүн яг нэг ерөнхий найзтай бол бүх хүнийг таньдаг нэг хүн олдоно гэж батал.

Бодолт 2.

1. Эхлээд дурын А, Б гэсэн найз биш хоёр хүнийг авч үзье. А-ын найзуудыг a_1 ... a_k Б-ын найзуудыг b_1...b_l гэе. f(i) -ээр a_i ба Б-ын ерөнхий найзын индексийг тэмдэглэе. Адилаар g(j)-ээр А ба b(j)-ын ерөнхий найзын индексийг тэмдэглэе. Тэгвэл f ба g нь бие биеийнхээ урвуу буулгалт болно, эндээс А ба Б нь ижилхэн тооны найзуудтай.

2. Үүний дараа эсрэг граф (найз биш хүмүүсээр үүссэн граф)-ыг холбоост гэж батлана. (Холбоост биш гэж үзвэл нийгэмлэг ганц хүнтэй болоход хүрч зөрчил. өөрөө шалган уу).
3. Иймд бүх хүмүүс адил тооны найзуудтай болох ба үүнийг d-ээр тэмдэглэе. Нийгэмлэгийн бүх хүний тоо n байг. Эндээс n=d^2-d+1 гэж гаргана.

4. c(p)-ээр p урттай циклийн тоог тэмдэглэе. Эндээс c(p)=n\cdot d^{p-2}+(d-1) \cdot c(p-2) гэсэн рекурент томьёо гаргана.
5. d-1-ын анхны тоон хуваагч p байг. Тэгвэл c(p)=n=1(mod p) болно. Нөгөө талаас p урттай циклийн тоо p-д хуваагдах ёстой. Эндээс зөрчил үүсч байгаа тул d-1 нь анхны тоон хуваагчгүй болж d=2 эндээс n=3 гэж гарч ерөнхий найз орших нь батлагдлаа.
Саяны баталгаа нийгэмлэг төгсөглөг хүнтэй үед батлагдсан. Харин төгсгөлгүй хүнтэй нийгэмлэг дээр бодлого хүчинтэй эсэсхийг мэдэхгүй байна.

Сэтгэгдэл бичих