Граф тухай

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

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

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

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

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

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

Граф нь тодорхойлолтоосоо хамааран талууд нь жин（өртөг）-тэй байж болно. Ийм графыг Жинтэй граф гэж нэрлэнэ. 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 байх оройг Саланги цэг гэдэг.

Хөрш оройнуудаар дамжсан v1, e1, v2, e2, …, en-1, vn дарааллыг зам, нэг ч тал давхардаж ороогүй бол энгийн зам гэдэг. Мөн эхлэл, төгсгөл нь давхцах замыг битүү зам（цикл） гэнэ.

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

ГРАФЫН ОНОЛЫН БУСАД ОЙЛГОЛТУУД

Граф бол ялангуяа Комьютерийн шинжлэх ухааны маш том мөн маш чухал хэсэг юм. Графын бодлого тэмцээн уралдаануудад маш олон төрөл, өгөгдөлийн бүтэцтэйгээр орж ирж байна. Энгийнээс нь дурьдвал 2 хэмжээст хавтгайд 2 хотын хоорондох замыг олох бодлогоос эхлээд өөр өөрийн хэмжээтэй усны сувгаар холбогдсон байгууламжаар хамгийн ихдээ хэдэн литр усыг зөөж чадах вэ? гэх хэцүү бодлого хүртлээ явна. Зөв өгөгдлийн бүтэц сонгох нь бодолтын ажиллах хугацаа, ашиглах санах ой зэрэгт нөлөөлөх хамгийн том зүйл, мөн кодоо цэвэрхэн бичих нь бас л туршлага, цаг хугацаа шаардагдах зүйл.  Граф бол энгийн үгээр хотууд болон тэдгээрийн хоорондох замууд гэж ойлогож болно. Тэгэхээр зүгээр л хоорондоо холбоотой хотуудыг холбож дүрслэхийг энгийн граф. Мөн мэдээж А хотоос Б хот хүрэхэд С км явж хүрдэг байг. Тэгвэл графыг ийм хоорондох зайтай нь дүрсэлсэн бол Жинтэй Граф гэнэ. Тэгвэл дахиад графыг хот чиглэлтэй нь дүрслэхийг Чиглэлт Граф эсрэг тохиолдолд Чиглэлгүй Граф гэнэ. Жишээ нь А Б хот нь хөрш хотууд ба А-аас Б хүрэх зам байдаг ба харин Б хотоос А хүрэх шууд зам байдаггүй байж болно. Үүнийг л чиглэлт граф гэнэ. Тэгэхээр Чиглэлт Графын хувьд А->Б байхад Б->А байх албагүй, Чиглэлгүй Графын хувьд бол A->Б, Б->А байх нь тодорхой. Дараах төрлөөр графуудыг тодорхойлоно:

• Чиглэлгүй Граф Энд 3-н оройтой 3-н ирмэгтэй Чиглэлгүй Граф байна.

• Чиглэлт Граф Энд 3-н оройтой 3-н ирмэгтэй Чиглэлт Граф байна.
• Давхар Граф – энд А хотоос Б хот хүрэх 2-оос олон зам байж болно.
• Жинтэй Граф

 Цикл гэдэг нь Ямар нэгэн хотоос гараад өгөгдсөн ирмэг-замуудыг ашиглаад анх гарсан хот дээрээ ирж чадаж байвал Цикл байна гэнэ. Тэгвэл Графын хувьд зэрэг гэж юуг хэлэх вэ? Зэрэг гэдэг нь тухайн оройгоос гарсан болон тухайн орой дээр ирсэн ирмэгүүдийн тоог хэлнэ. Зэрэг нь 2 янз байх ба Дотоод зэрэг, Гадаад зэрэг. Дотоод зэрэг нь тухайн оройгоос гарсан ирмэгүүдийн тоо, харин дотоод ирмэгүүдийн тоо нь тухайн оройруу ирсэн чиглэлтэй ирмэгүүдийн тоог хэлнэ. Дээрх Графын хувьд орой болгоны хувьд Дотоод, Гадаад ирмэгүүдийг тэмдэглэсэн байна. Одоо дараагийн асуудал Компьютерт Графыг яаж таниулах вэ? Дараах 2 үндсэн дүрслэлийг тайлбарлая. Хөршийн Матриц: Энд бид нар хамгийн энгийн өгөгдөлийн бүтэц төрөл болох Массив ашиглана. Ерөнхийдөө бол бид V[N][N] энд N-оройн тоо, хэмжээтэй массив ашиглана. V[i][j]-ээр i хотоос j хот хоорондоо холбогдсон эсэхийг тэмдэглэнэ. Тэгэхээр Чиглэлгүй Граф жингүй Граф бол V[i][j]=V[j][i]=1, Чиглэлтэй Жингүй Граф-д V[i][j]=1 байхад V[j][i]=1 байх албагүй. Харин Жинтэй граф байвал V[i][j] = w, энд w нь жин. Дээрх Граф ямар Граф байна? Мэдээж Жинтэй Чиглэлт Граф. Одоо массивдаа ирмэг болон жинг хадлгалахыг харцгаая.

A  B  C

A   0  1  5

B  -1  0  1

C  -1 -1  0

Бидэнд өөрөөсөө өөрлүүгээ татсан ирмэгтэй граф байж болно. Үүнийг Гогцоо гэдэг юм.  Дээрх графын хувьд Гогцоо байхгүй. Мөн хэрэв та лавшруулж бодсон бол Жинтэй графын хувьд хоорондоо ирмэг байхгүй бол юу гэж тэмдэглэх вэ? гэж бодогдоно. Энд тооцох ёстой бол тухайн өгөгдсөн граф-д сөрөг жин өгөгдөх эсэхээс шалтгаална. Хэрэв Сөрөг жин байхгүй гэж өгөгдвөл хоорондоо ирмэггүй хотуудыг зүгээр л -1ээр тэмдэглэчих. Дээрх граф маань сөрөг жин байхгүй гэж үзсэн байна. Харин сөрөг жин байгаа гэсэн бол хоорондоо ирмэггүй хотуудыг маш том тоогоор буюу граф-н жингийн хязгаарлалтаас том тоогоор INF = 2^32-1 тэмдэглэ.  Энэ аргын сул тал бол санах ойд N*N*(өгөгдлийн төрөл) шаардах ба хугацааны хувьд санах ойд зүгээр л дүрслэхэд л O(N^2) хугацаа шаардна. Дараагийн арга бол маш үр дүнтэй аргуудын нэг. Хөршүүдийг жагсаах арга: Энд vector-г ашиглах нь тохиромжтой. Бид N-оройн тоо ширхэг Вектор ашиглах ба i Вектор тус бүр тухайн i оройн бүх хөрш оройнуудыг жагсааж хадгална. Дээрх жишээн хувьд бидэн 4-н Вектор хэрэг болох ба дараах байдлаар дүрслэнэ.
V[1] = {2, 3};
V[2] = {1};
V[3] = {1, 4};
V[4] = {1, 3};
Дээрх Граф маань чиглэлгүй, жингүй цикл агуулсан граф байлаа. 

// 3 4

// 1 2

// 2 3

// 3 4

// 1 4

#include<cstdio>

#include<cstdlib>

usingnamespace std;

int v[100][100];

int n, m;

int main(){

scanf(“%d%d”, &n, &m);

while(m–){

int a, b;

scanf(“%d%d”, &a, &b);

a–;–b;

v[a][b]=1;