Графтар теориясының негізгі анықтамалары Қолдану мысалдары

Графты сыбайлас матрица арқылы көрсету

жүктеу/скачать 291,42 Kb.

бет	2/5
Дата	27.04.2023
өлшемі	291,42 Kb.
	#175595

1 2 3 4 5

Байланысты:
23-24 Графтар 1

Графты сыбайлас матрица арқылы көрсету
Сыбайлас матрицада жолдар мен бағаналар саны төбелер санына тең.
Қиылыста осы төбелердің байланысын сипаттайтын мән орналасады, мысалы, егер қабырға болса, онда 1-ге, егер қабырға жоқ болса, онда 0-ге тең.
Графтар үшін сыбайлас матрицада жолдар мен бағаналар саны төбелер санына тең.
Қарапайым бағытталмаған граф
Сыбайлас матрица
Графты сыбайлас матрица арқылы көрсету
Бағытталған графтар үшін сыбайлас матрицада жолдар мен бағаналар саны төбелер санына тең.
Қиылыста осы төбелердің байланысын сипаттайтын мән орналасады, мысалы, егер сәйкес төбелер арасында байланыс бар болса, онда 1-ге, егер байланыс жоқ болса, онда 0-ге тең.
Бағытталған графтың сыбайлас матрицасы
Бағытталған граф
Графты жұптар тізімі түрінде көрсету. Графты төбелердің сыбайлас жұптарының тізімі түрінде көрсету. Мысалы, жоғарыда ұсынылған графтарды төбелердің сыбайлас жұптарының тізімімен көрсетуге болады.
Графты сыбайлас матрица арқылы көрсету
1-граф 2-граф
1) 1 – 2 1 – 2
2) 1 – 4 1 – 3
3) 1 – 5 3 – 2
4) 2 – 3 3 – 4
5) 2 – 4 5 – 4
6) 3 – 5 5 – 6
7) 3 – 6 6 – 5
8) 4 – 5 1– 2
9) 5 – 6 1– 2
Осы тізімдерді ЭЕМ жадында екі өлшемді массив түрінде көрсетуге болады. ЭЕМ жадында графтарды осы жолмен сақтау ең тиімді болып есептеледі, бірақ жұмыс жасауға үнемі қолайлы бола бермейді.
int[,] a = new int[6,6]
{
{0,3,1000,3,6,1000},
{1000,0,4,7,1000,4},
{3,8,0,5,1000,2},
{1000,6,1000,0,3,1000},
{7,1000,1,4,0,4},
{5,2,1000,1000,2,0}
};
Флойд алгоритмі
Графтар теориясында граф төбелерінің арасындағы ең қысқа арақашықтықты анықтайтын көптеген алгоритмдер белгілі, бірақ оның барлығы Флойд ұсынған алгоритмді негізге алады.
Осы алгоритмнің кең қолданылуы төбелер арасындағы ең қысқа арақашықтықты табу идеясында, бірақ есептеу бойынша Флойд алгоритмінің тиімділігі өте төмен.
Флойд алгоритмі
Бағытталған граф
Флойд алгоритмін қарастырайық.
6 төбесі бар бағытталған граф бар болсын, келесі суретте көрсетілген.
Флойд алгоритмі
Графтың сыбайлас матрицасы
Осы графтың сыбайлас матрицасы келесі кестесінде көрсетілген:
Кесте –12.4-суреттегі графтың сыбайлас матрицасы
Флойд алгоритмінің идеясы бойынша әрбір a[i,j] – төбелер жұбына k (0 – 5) төбелерінің барлық мүмкін нұсқалары мына түрде тексеріледі: a[i,j]>a[i,k]+a[k,j].
Егер a[i,j] жолы үлкен болса, онда сыбайлас матрицада i және j төбелерінің арасындағы жолдың мәні a[i,k]+a[k,j] жолына тең жаңа мәнмен ауыстырылады. Сонымен, ең қысқа қашықтықты анықтайтын матрица дайын болды.
Мысалы, сыбайлас матрицада 2-шіден 1-г дейін жол 8-ге (2-1) тең. Бірақ, егер біз бірінші 0-ге, ал содан кейін 1-ге орын ауыстыратын болсақ, онда жол 6-ға тең болады: a[2,0]+a[0,1]= 3+3=6.
Барлық нұсқаларды тексере отырып, біз мынаны байқадық: 2-5-1 жолы қысқарық, a[2,5]+a[5,1]=2+2=4.
Флойд алгоритмі
static void Main()
{
int[,] a = new int[6,6]
{{0,3,1000,3,6,1000},
{1000,0,4,7,1000,4},
{3,8,0,5,1000,2},
{1000,6,1000,0,3,1000},
{7,1000,1,4,0,4},
{5,2,1000,1000,2,0}};
int i,j,w,n,k;
Console.WriteLine("Печатаем исходную матрицу : ");
for (i=0;i<6;i++)
{
for (j=0;j<6;j++)
Console.Write("\t" + a[i,j]);
Console.WriteLine();
}
Console.WriteLine();

жүктеу/скачать 291,42 Kb.

Достарыңызбен бөлісу:

1 2 3 4 5