بخشی از پاورپوینت
اسلاید 1 :
تعاريف
- مجموعه اي غير تهي از راس
- مجموعه اي از زوج راسها كه بوسيله يال بهمديگر متصل هستند.
اسلاید 2 :
انواع گراف
- گراف بدون جهت Undirected graph
- گراف جهت دار Directed graph
- گراف چند ياليMulti-graph
- گراف كاملComplete Graph
- گراف ساده Simple graph
اسلاید 3 :
نمايش گراف
- ماتريس همجواري Adjacency Matrix
- ماتريس اتصال Incidence Matrix
- ليستهاي مجاورتي
- آرايه
- ليستهاي مجاورتي چند گانه
- ...
اسلاید 4 :
ماتريس همجواري
- There is an N x N matrix, where |V| = N , the Adjacenct Matrix (NxN) A = [aij]
- For undirected graph
- For directed graph
- This makes it easier to find subgraphs, and to reverse graphs if needed.
اسلاید 5 :
پيمايش گراف
- هدف ديدن تمامي نود هاست
- استفاده از ساختمان داده استك يا صف
- پيمايش يا جستجوي عمقي Depth-First-Search (DFS)
- پيمايش يا جستجوي سطحي Breadth-First-Search (BFS)
اسلاید 6 :
سوالات
- به كمك پيمايشها روشي بيابيد كه متصل بودن گراف را تشخيص دهد.
- گراف دو بخشي: چگونه دو بخشي بودن گراف را تشخيص دهيم.