Графын онол

Графын онол нь орой болон тал （мөчир）-уудын олонлогоос тогтох Граф гэх зүйлийн мөн чанарыг судалдаг математикийн нэг салбар ухаан юм.

Компьютерийн Өгөгдлийн бүтэц болон алгоритм зэрэгт өргөнөөр хэрэглэгддэг.

Граф

Галт тэрэг ашиглан нэг өртөөнөөс нөгөөд очиход уг 2 өртөө （орой） нь төмөр зам (тал) -аар холбогдсон эсэхийг мэдэх хэрэгтэй болохоос төмөр замын сүлжээ нь ямар хэлбэр дүрс үүсгэж байгаа нь чухал биш байх нь олонтаа.

Тийм ч учраас улс орнуудын төмөр замын сүлжээний зурагт өртөө хоорондын зай, өртөөнүүдийн байршил, зам зэргийг жинхэнээс нь ялгаатай дүрсэлсэн байх тохиолдол олон.

Ийнхүү хэрхэн холбогдож байгааг нь голлон анхаарч бий болгосон цэг ба тэдгээрийг холбох шугамуудаас бүтэх хийсвэр дүрс нь граф бөгөөд графын шинж чанарыг графын онолд судалдаг.

6 орой, 7 талаас тогтох графын жишээ

Хэрэв төмөр замын холбогдсон зам нь ганцхан чиглэлтэй бол нэг өртөөнөөс нөгөөд очиж болдог байхад буцаж очих боломжгүй байж болно. Ийнхүү төмөр замд чиглэл гэсэн ойлголт нэмж болно. Үүнтэй адилаар графын онолд талд чиглэл оноож болдог. Ийм графыг чиглэлт граф гэнэ. Эсрэгээр, талууд нь чиглэлгүй бол чиглэлгүй граф гэж нэрлэдэг.

Графын жишээ

Төмөр замын сүлжээний зураг

Цахилгааны шугам

WWW-ийн бүтэц

WWW дэх цахим хуудаснуудын хоорондын холбоосыг харуулсан зураг нь чиглэлт граф болно.

Графын онолын үүсэл

Графын онол нь 1736 онд "Кёнигсбергийн бодлого"-ыг Леонард Эйлер шийдсэнээс эхлэлтэй. Энэхүү бодлого нь үзэг салгалгүй зурахтай гүнзгий холбоотой юм.

Графын математик тодорхойлолтууд

Чиглэлт граф

$V$ нь оройнуудын олонлог, $E$ нь талуудын олонлог байг. Талуудыг оройнуудын хост харгалзуулдаг $f$ функц тодорхойлогдсон гэж үзье.

$f:E\to V\times V$.

Тэгвэл чиглэлт граф $G$ нь

$G:=(f,~V,~E)$

гэж тодорхойлогдоно.

Чиглэлгүй граф

$P(''V'')$ нь $''V''$ -ийн бүх дэд олонлогуудын олонлог байг. Талд хэд хэдэн оройг харгалзуулдаг g функц оршин байг.

$g:E\to P(V)$

Энд дурын $''e''$ талын хувьд g(e) = (v₁, v₂) хэлбэрээр 2 орой харгалздаг гэж үзье. Тэгвэл чиглэлгүй граф G нь

$''G'':=(''g'',''V'',''E'')$

гэж тодорхойлогдоно. g нь 3-аас олон оройг талд харгалзуулдаг функц байвал уг графыг хайпэр граф гэдэг.

E-г анхнаасаа ямар нэг олонлогийн дэд олонлог гэж үзвэл дээрх тодорхойлолтоос функцийг нь хасч болно. Үүний тулд чиглэлт графт E-г V×V-ийн дэд олонлог, чиглэлгүй графт E-г P(V)-ийн дэд олонлог гэж ойлгоход болно.

Үндсэн ойлголтууд

Граф нь тодорхойлолтоосоо хамааран талууд нь жин（өртөг）-тэй байж болно. Ийм графыг Жинтэй граф гэж нэрлэнэ. G графын оройнуудын олонлогийг V(G)、талуудын олонлогийг E(G) гэж тэмдэглэх нь элбэг.

e талын холбож буй оройнуудыг төгсгөлүүд гэх бөгөөд тэдгээр нь e-гээр хөрш гэж хэлнэ Мөн нэг оройгоос гарсан 2 талыг зэргэлдээ талууд гэнэ. Хэрэв талын 2 төгсгөл нь давхцаж байвал уг талыг гогцоо гэдэг. Бас 2 оройг холбосон тал хэд хэд байвал тэдгээр талыг давхар замууд гэнэ. Гогцоо болон давхар замгүй графыг энгийн граф гэдэг.

G ба G' графуудын хувьд G' -ийн оройнуудын болон талуудын олонлог нь харгалзан G-ийн оройнуудын болон талуудын олонлогийн дэд олонлог байвал G' -г G-ийн дэд граф гэж нэрлэдэг. Эсрэгээрээ, G нь G' -ийн өргөтгөсөн граф гэдэг. Тухайлбал уг 2 графын оройнуудын олонлог нь давхцаж байвал нэг нь нөгөөгийнхөө үржигдэхүүн граф гэнэ.

Графын ямар нэг v орой төгсгөл нь болдог талуудын тоог уг оройн эрэмбэ гээд d(v) гэж тэмдэглэнэ. Түүнчлэн чиглэлт графын хувьд v оройгоос гарсан талуудын тоог v-ийн гарсан эрэмбэ, хүрч ирсэн талуудын тоог v-ийн орсон эрэмбэ гэнэ. Дурын v оройн хувьд d(v) = k гэсэн нөхцөл биелж байвал k-зөв граф гэнэ. k-ийн хувьд k-зөв графыг товчоор зөв граф гэдэг. G графын хамгийн бага эрэмбэ бүхий оройн тоог δ(G), хамгийн их эрэмбэ бүхий оройн тоог Δ(G)-ээр тэмдэглэх нь элбэг. Мөн эрэмбэ нь 0 байх оройг Саланги цэг гэдэг.

Хөрш оройнуудаар дамжсан v₁, e₁, v₂, e₂, ..., e_n-1, v_n дарааллыг зам, нэг ч тал давхардаж ороогүй бол энгийн зам гэдэг. Мөн эхлэл, төгсгөл нь давхцах замыг битүү зам（цикл） гэнэ.

Дурын 2 орой нь талаар шууд холбогдсон байвал бүтэн граф гэх бөгөөд n оройтой бүтэн графыг K_n-ээр тэмдэглэдэг.

Графын онолын бусад ойлголтууд

• Эйлерийн зам （Эйлерийн битүү зам, Эйлерийн граф）
• Хамильтоны зам （Хамильтоны битүү зам, Хамильтоны граф）
• Мод
• Диаметр
• Холбоост граф
• Хавтгай граф
• Хөршийн матриц

Бодлогууд, асуудлууд

• Хамгийн бага замын бодлого
• Хамильтоны битүү замын бодлого
• Штейнерийн мод
• Дөрвөн өнгийн теорем
• Өнгөт бүтэн графын теорем

Хэрэглээ

• Үхлийн цоожийг олох
• Гарбэж коллекшн
• Файлын систем
• Хуудсыг эрэмбэлэх

Мөн үзэх

• Рамсейн онол
• Жижиг ертөнцийн үзэгдэл
• Комбинаторик

Энэ математикийн тухай өгүүлэл дутуу дулимаг бичигджээ. Нэмж гүйцээж өгөхийг хүсье.