|
Yo'nalgan graflar matritsalari, yo'l tushunchasi.Graflar izomorfligi, misollar bilan
|
| bet | 3/7 | | Sana | 09.01.2024 | | Hajmi | 0,74 Mb. | | #132798 |
Bog'liq DISKRET 5 M - Yo'nalgan graflar matritsalari, yo'l tushunchasi.Graflar izomorfligi, misollar bilan.
- Yonalgan graflar matritsalari va yo'l tushunchasi, graflar izomorfligi bilan bog'liq mavzular o'rin oladi. Bu mavzularni quyidagi tarzda tushunishimiz mumkin:
- 1. Yonalgan Graflar Matritsalari:
- Yonalgan graflar matritsalari quyidagi xususiyatlarga ega bo'ladigan ma'lumotlardir:
- Adjacency Matrix (Adjacency Matrix): Bu matritsa, grafning uchlari orasidagi aloqalarni ifodalaydi. Matritsani o'qiash orqali, uchlar orasidagi aloqalarni aniqlash mumkin. Agar grafda uchlar bir-biriga bog'langan bo'lsa, matritsa ijodiy sonlarni o'z ichiga olishadi, aks holda 0 yoki -1 (masalan, bo'sh joy) ifodalaydi. - Adjacency Matrix (Adjacency Matrix): Bu matritsa, grafning uchlari orasidagi aloqalarni ifodalaydi. Matritsani o'qiash orqali, uchlar orasidagi aloqalarni aniqlash mumkin. Agar grafda uchlar bir-biriga bog'langan bo'lsa, matritsa ijodiy sonlarni o'z ichiga olishadi, aks holda 0 yoki -1 (masalan, bo'sh joy) ifodalaydi. - Incidence Matrix (Incidence Matrix): Bu matritsa, grafning uchlarini va yollarini ifodalaydi. Uchlar va yo'li orasidagi bog'lanishni ifodalaydi. Agar uch grafning uchidan birida yo'l (yoki boshqa aloqador ob'ekt) bor bo'lsa, matritsa o'z ichiga 1 yoki -1 (yo'lni tushuntirish uchun) ifodalaydi. 2. Yo'l Tushunchasi: - 2. Yo'l Tushunchasi:
- Yo'l tushunchasi, grafda uchlar orasida yo'l olishning amaliy yuzasini ifodalaydi. Yo'l tushunchasi, bir uchdan boshlab boshqa uchga yo'l olish uchun kerak bo'lgan qadamni aniqlash uchun foydalaniladi.
- - Graflar Izomorfligi:Graflar izomorfligi, ikki yonalgan graf o'zaro bir-biriga o'xshash bo'lgan, ammo uchlari va bog'lanishlari qanday qilib tuzatilganligini aniqlashda foydalaniladi.
Misollar: - Misollar:
- - Misol 1 (Adjacency Matrix): Quyidagi matritsa A bir grafning yonalgan matritsasi bo'lsa:
- ```
- A = | 0 1 1 |
- | 1 0 0 |
- | 1 0 0 |
- ```
- Ushbu matritsada uchlar bir-biriga bog'langan.
|
| |
