Граф - 1

За сайн байцгаана уу.
Одооноос ерөнхийдөө Төлөвлөгөө постыг даган блогоо хөтлөх болноо.

Эхлээд Графын тухай энгийн оршил бичие:
Граф бол ялан гуяа Комьютерийн шинжлэх ухааны маш том мөн маш чухал хэсэг юм. Графын бодлого тэмцээн уралдаануудад маш олон төрөл, өгөгдөлийн бүтэцтэйгээр орж ирж байна. Энгийнээс нь дурьдвал 2 хэмжээст хавтгайд 2 хотын хоорондох замыг олох бодлогоос эхлээд өөр өөрийн хэмжээтэй усны сувгаар холбогдсон байгууламжаар хамгийн ихдээ хэдэн литр усыг зөөж чадах вэ?(энэ бодлогыг Урсгалын - Maximum Flow Min Cut бодлого гэдэг ба нилээн туршлагатай, шаардлагатай өгөгдлийн бүтэц алгоритмыг тайлбарлсны дараа тайлбарлагдах бодлого) гэх хэцүү бодлого хүртлээ явна. Зөв өгөгдлийн бүтэц сонгох нь бодолтын ажиллах хугацаа, ашиглах санах ой зэрэгт нөлөөлөх хамгийн том зүйл, мөн кодоо цэвэрхэн бичих нь бас л туршлага, цаг хугацаа шаардагдах зүйл. Гэхдээ азаар одоогийн ихэнх програмчлалын хэлүүд ихэнх том том өгөгдөлийн бүтцүүдийг бэлдээд өгцөн байгаа, гэхдээ бид нар онолыг нь сайн ойлгоод эзэмших хэрэгтэй. Мэдээж сурахад тийм ч амар биш, гэхдээ энгийн сэтгээд жаахан цаг гаргаад суухад сурахад ямар ч асуудал байхгүй.

За Граф бол энгийн үгээр хотууд болон тэдгээрийн хоорондох замууд гэж ойлогож болно. Тэгэхээр зүгээр л хоорондоо холбоотой хотуудыг холбож дүрслэхийг энгийн граф. Мөн мэдээж А хотоос Б хот хүрэхэд С км явж хүрдэг байг. Тэгвэл графыг ийм хоорондох зайтай нь дүрсэлсэн бол Жинтэй Граф гэнэ. Тэгвэл дахиад графыг хот чиглэлтэй нь дүрслэхийг Чиглэлт Граф эсрэг тохиолдолд Чиглэлгүй Граф гэнэ. Жишээ нь А Б хот нь хөрш хотууд ба А-аас Б хүрэх зам байдаг ба харин Б хотоос А хүрэх шууд зам байдаггүй байж болно. Үүнийг л чиглэлт граф гэж байгаам. Тэгэхээр Чиглэлт Графын хувьд А->Б байхад Б->А байх албагүй, Чиглэлгүй Графын хувьд бол 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};
Дээрх Граф маань чиглэлгүй, жингүй цикл агуулсан граф байлаа.
Одоо C++ дээрх кодоор сонирхуулаад энэ постоо дуусгая. Асууж тодруулах юмаа коммент бичээд асуучаарай, ойлгомжтой байлгахын тулд аль болох энгийн өөрийн үгээр тайлбарлахыг хичээлээ, мөн дараагийн пост маань Түвшний нэвтрэлт, түүнд хэрэглэгдэх өгөгдөлийн бүтцийн хамт байх болно.

// Chiglelgui Jingui N oroitoi M irmegtei Graph-g 
//Horshiin matrix ashiglan com-d durselj baina!
// Orolt daraahi helbertei:
// 3 4
// 1 2
// 2 3
// 3 4
// 1 4
#include<cstdio>
#include<cstdlib>
using namespace 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;
        v[b][a]=1;//Chigleltei Graph gesen bol ene mor hereggui!!
    }
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++)
           printf("%d ", v[i][j]);
        printf("\n");
    }
    system("pause");
return 0;}

// Chiglelgui Jintei N oroitoi M irmegtei Graph-g 
//Horshiin matrix ashiglan com-d durselj baina!
// Orolt daraahi helbertei:
// 3 4
// 1 2 3
// 2 3 2
// 3 4 4
// 1 4 2
#include<cstdio>
#include<cstdlib>
using namespace std;
int v[100][100];
int n, m;
int main(){
    scanf("%d%d", &n, &m);
    while(m--){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        a--;--b;
        v[a][b]=c;
        v[b][a]=c;//Chigleltei Graph gesen bol ene mor hereggui!!
    }
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++)
           printf("%d ", v[i][j]);
        printf("\n");
    }
    system("pause");
return 0;}

// Chiglelgui Jintei N oroitoi M irmegtei Graph-g 
//Horshiin jagsaalt ashiglan com-d durselj baina!
// Orolt daraahi helbertei:
// 3 4
// 1 2 3
// 2 3 2
// 3 4 4
// 1 4 2
#include<cstdio>
#include<cstdlib>
#include<utility>
#include<algorithm>
#include<vector>
using namespace std;
int n, m;
vector< pair<int, int> >v[101];
int main(){
    scanf("%d%d", &n, &m);
    while(m--){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        a--;--b;
        v[a].push_back(make_pair(b, c));
        v[b].push_back(make_pair(a, c));//Chigleltei Graph gesen bol ene mor hereggui!!
    }
    for(int i=0; i<n; i++){
        printf("%d -> ", i+1);
        for(int j=0; v[i].size(); j++)
           printf("%d %d", v[i][j].first+1, v[i][j].second);
        printf("\n");
    }
    system("pause");
return 0;}