Qrafik təpələr və kənarlardan ibarətdir. Təpələr müəyyən bir xassəyə görə kənarlarla birləşdirilir - kənarların dəstini təyin edən insidensiya əlaqəsi. Bu vəziyyətdə, döngələr və təcrid olunmuş təpələr meydana gələ bilər.
Təlimat
Addım 1
Qrafın kənar dəsti verilsin və boyunca bir təpədən digərinə kənar çəkmək mümkün olan münasibət verilsin. Nümunə olaraq, {1, 2, 3, 4, 5, 6, 7, 8} təpələri çoxluğu, iki x və y təpələri x + y <8 nisbətindədir.
Addım 2
Bir təpə bitişikliyi matrisi yaradın. Bunu etmək üçün bir kvadrat masa düzəldin, cədvəldəki sətir və sütunların sayı zirvələrin sayı ilə üst-üstə düşür. Sonra i və j təpələri verilmiş nisbəti təmin edərsə, i-ci sıra ilə j-ci sütunun kəsişməsində 1 qoyun. Müvafiq elementlər üçün nisbət yerinə yetirilmədiyi təqdirdə i-ci sətir və j-sütunun kəsişməsində 0 qoyun.
Bizim nümunəmizdə birinci sətir belə doldurulur:
1 + 1 <8, buna görə 1-ci sıra ilə 1-ci sütunun kəsişməsində 1 var
1 + 2 <8, yenidən 1
1 + 3 <8, yenidən 1
1 + 7 <8, səhv bərabərsizlik, buna görə cədvəlin bu elementi 0 olacaqdır
1 + 8 <8, yenidən 0
Addım 3
Kənarların sayını tapmaq üçün, kənarları təkrarlamadan bitişiklik matrisində olanların sayını hesablayın.
Nümunədə simmetrik bir matris əldə edildi, buna görə əvvəlcə matrisin əsas diaqonalından yuxarı olanları (mavi ilə işarələnmiş), sonra əsas diaqonaldakıları (qırmızı ilə işarələnmiş) saydıq. Ümumi qabırğa sayı 12-dir.
Addım 4
Hadisələrin (kənarların) matrisini yaradın. Bunu etmək üçün bir cədvəl çəkin, içindəki sətirlərin sayı qrafikdəki zirvələrin sayına, sütunların sayı isə kənarların sayına bərabərdir. Bir kənarla birləşdiriləcək xətlərə vahidlər qoyun. Təpədən ona gedən kənarlara döngələr deyilir və matrisin sonuna əlavə olunur. Döngələrə uyğun sütunlarda, qalan kənarların əksinə, yalnız bir vahid var.
Addım 5
İndi bir qrafik çəkin. Küncləri hər hansı bir şəkildə kağıza qoyun və qurulmuş cədvəllərdən istifadə edərək kənarları ilə birləşdirin. Kənarları ilə birləşdirilməyən diklərə təcrid olunmuş deyilir.
