گراف

گراف

اسلاید 1: گرافوحيدي پور

اسلاید 2: تعاريفمجموعه اي غير تهي از راسمجموعه اي از زوج راسها كه بوسيله يال بهمديگر متصل هستند.abde

اسلاید 3: انواع گرافگراف بدون جهت Undirected graphگراف جهت دار Directed graphگراف چند ياليMulti-graphگراف كاملComplete Graphگراف ساده Simple graphUndirected graphDirected graphisolated vertexadjacentloopG=(V,E)

اسلاید 4: تعاريفpath: no vertex can be repeated a-b-c-d-etrail: no edge can be repeat a-b-c-d-e-b-dwalk: no restriction a-b-d-a-b-cclosed if x=yclosed trail: circuit (a-b-c-d-b-e-d-a, one draw without lifting pen)closed path: cycle (a-b-c-d-a)length: number of edges inthis (path,trail,walk)abde

اسلاید 5: abcdeabcdebcdeacdزير گراف

اسلاید 6: ADT گرافObject: A non-empty set of vertices and a set of undirected edges where each edge is pair of vertices.Graph(); // create an empty graphInsert-vertex();Delete-vertex();Insert-edge();Delete-edge();IsEmpty();

اسلاید 7: نمايش گرافماتريس همجواري Adjacency Matrixماتريس اتصال Incidence Matrixليستهاي مجاورتيآرايهليستهاي مجاورتي چند گانه...

اسلاید 8: ماتريس اتصالIncidence matrixLabel rows with verticesLabel columns with edges1 if an edge is incident to a vertex, 0 otherwiseefghjv11000w10101x00011y01110

اسلاید 9: ماتريس همجواريThere is an N x N matrix, where |V| = N , the Adjacenct Matrix (NxN) A = [aij] For undirected graph For directed graphThis makes it easier to find subgraphs, and to reverse graphs if needed.

اسلاید 10: ماتريس همجواري - مثالExample: Undirected Graph G (V, E)uvw

اسلاید 11: بستار انتقاليحاصلضرب متوالي ماتريس همجواري

اسلاید 12: لستهاي مجاورتيEach node (vertex) has a list of which nodes (vertex) it is adjacentExample: undirectd graph G (V, E)uvw

اسلاید 13: استفاده از آرايهگراف در آرايه اي بنام Node ذخيره مي شود.N نود گراف در ابتداي آرايه قرار مي گيرندشماره نودهاي متصل به نود iام در خانه هاي Node[Node(i)] تا Node[Node(i+1)] قرار دارد.اين آرايه چند خانه دارد؟01342

اسلاید 14: ليستهاي چند گانه مجاورتي

اسلاید 15: پيمايش گرافهدف ديدن تمامي نود هاستاستفاده از ساختمان داده استك يا صفپيمايش يا جستجوي عمقي Depth-First-Search (DFS)پيمايش يا جستجوي سطحي Breadth-First-Search (BFS)

اسلاید 16: سوالاتبه كمك پيمايشها روشي بيابيد كه متصل بودن گراف را تشخيص دهد.گراف دو بخشي: چگونه دو بخشي بودن گراف را تشخيص دهيم.