گراف

صفحه 1:
گراف وحيدي پور 

صفحه 2:
تعاریف ‎٠‏ مجموعه اي غير تهي از راس ‎٠‏ مجموعه اي از زوج راسها كه بوسيله يال بهمديكر متصل ‎a 

صفحه 3:
انواع گراف گراف بدون جهت اموسب سل گراف جهت دار امي لس( گراف چند ياليامب-() گراف کاملبم<) عطا600 كراف ساده ‎raph‏ عامسر) ‎Undirected graph Directed graph‏ 1:0 G=(V,E) ° isolated vertex ‏بل‎ ac L—- 

صفحه 4:
تعاریف path: no vertex can be repeated b e a-b-c-d-e trail: no edge can be repeat a-b-c-d-e-b-d walk: no restriction d a-b-d-a-b-c length: number of edges in sed if x=y this (path, trail, walk) ‎trail: circuit (a-b-c-d-b-e-d-a,‏ ۵0و( ‎one draw without lifting pen)‏ ‎sed path: cycle (a-b-c-d-a)‏ 

صفحه 5:
زير گراف If G=(V, BisagrapitherG, =(V, (0 asubgrapif Gif ¢ #Y c Vand, ¢ & whereacledgef in & isincidentith vertésin Y. a d e c 

صفحه 6:
گرلف ject oP vertices und uo set oP ‏ار را ۱ انك‎ tenet oP ۳۲ ۱ // oreate oo exepty yraph ‏)یسیو‎ ‎Ortete-vertex(); ‏:)سلج سوه"‎ ODetete-edee(); 190): 

صفحه 7:
نمایش گراف * ماتریس همجواربي ‎Oduceuwy Duatric‏ + ماتریس ‎Dates Jail‏ ول * ليستهاي مجاورتي * ارایه * ليستهاي مجاورتي چند گانه 

صفحه 8:
0 oO 0 ماتريس اتصال 0 0 0 0 0 حول كلاب اس الا - ‎coed oo‏ و هلو مه 22 ) - ‎vertex, O verwiee‏ 

صفحه 9:
ماتریس همجواري Phere ig oa ۵0 ۵ ‏ی‎ where [O] = 0۵ , ۲ ‏و سوه‎ )00( - ‏لها‎ Cor vedrevted graph i if {v, v}isanedg@fG 0 otherwise ay = or drevied yropk 4 = 1if (v, w)isanedgefG 0 otherwise Dhis wwohes tt puster tp Pad subgraphs, oad to reverse qraphe f cerded, 

صفحه 10:
ماتریس همجواري - مثال ۰ ‏اه( تسام‎ Bropk © (O, ©) /\ PEE © 0 0 0 a 

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

صفحه 12:
لستهاي مجاورتي (Bock cede (verter) kos a bet of hick order (vertex) iti odkacect Exavple: undrertd qrupk B (O, &) 1 i 8 - 

صفحه 13:
استفاده از آرایه گراف در آرلیه اي بنام علم() ذخیره مي شود. نود گرلفدر لبتداآرلیه قرار مي‌گیرند شماره نودهاي متصل به نود رام 53 ‎Dode[Mode(#0)] 6 Dode[Dode(')] Ga SS‏ قرار دارد. این آرایه چند خانه دارد؟ 0 4 1 2 3 | | 6۱ ۱ ۱ ۵۱ ۱ ٩۱ 6۱ ۱ ۱ ۵۱ ۱ ٩۱ oe] a} aja ۵ | 9 | 6 6 oO 92 2 oO 5 oO 0 ٩] ٩۱ aaa] 0 Ro 

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

صفحه 15:
پیمایش گراف * هدف دیدن تمامي نود هاست * استفاده از ساختمان داده استك یا صف Oerpth-Pirst-Gearck ‏ييمايش يا جستجوي عمقي‎ ٠ (OG) * پیمایش با جستجوي سطحي ‎@reudth-Pirst-Grack‏ ‎(BPG)‏ 

صفحه 16:
سوالات ف‌ را گرا دن بیابید که ایشها رو ‎Lan‏ ‏: وت دهد اف چگونه بو فد را تشخیص بحسي بحسي فدرا ا كرا دن رم گوذ دو بخ ِ خشي: ج ف دو ب گرا دهیم. 

گراف وحيدي پور تعاريف • مجموعه اي غير تهي از راس • مجموعه اي از زوج راسها كه بوسيله يال بهمديگر متصل هستند. ‏a ‏e ‏d ‏b انواع گراف Undirected graph گراف بدون جهت Directed graph گراف جهت دار Multi-graphگراف چند يالي Complete Graphگراف كامل Simple graph گراف ساده Undirected graph Directed graph loop G=(V,E) isolated vertex adjacent • • • • • تعاريف a e path: no vertex can be repeated b a-b-c-d-e trail: no edge can be repeat a-b-c-d-e-b-d d walk: no restriction a-b-d-a-b-c length: number of edges in this (path,trail,walk) osed if x=y osed trail: circuit (a-b-c-d-b-e-d-a, one draw without lifting pen) osed path: cycle (a-b-c-d-a) زير گراف If G =(V, E) is a graph, then G1 (V1, E1) is called a subgraph of G if  V1  V andE1  E, where eachedgeof in E1 isincidentith w vertic esinV1. a e b a a d c b e b c e d d d c c فBراBBB گ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 graph • Insert-vertex(); • Delete-vertex(); • Insert-edge(); • Delete-edge(); • IsEmpty(); نمايش گراف • • • • • • ماتريس همجوارBي Adjacency Matrix ماتريس اتصال Incidence Matrix ليستهاي مجاورتي آرايه ليستهاي مجاورتي چند گانه ... ماتريس اتصال • Incidence matrix – Label rows with vertices – Label columns with edges – 1 if an edge is incident to a vertex, 0 otherwise j f e 0 0 0 1 1 1 0 1 0 1 w 1 h g v 1 0 0 0 x 0 1 1 1 0 y ماتريس همجواري  There is an N x N matrix, where |V| = N , the Adjacenct Matrix (NxN) A = [aij]  For undirected graph 1 if {vi, vj}isanedgeof G a ij  0 otherwise  For directed graph 1 if (vi, vj) isanedgeof G a ij  0 otherwise  This makes it easier to find subgraphs, and to reverse graphs if needed.  مثال- ماتريس همجواري • Example: Undirected Graph G (V, E) u v w w u v 1 1 0 v 1 0 1 u 0 1 1 w بستار انتقالي • حاصلضرب متوالي ماتريس همجواري لستهاي مجاورتي Each node (vertex) has a list of which nodes (vertex) it is adjacent Example: undirectd graph G (V, E) Adjacency List u v w node v,w u w, u v u,v w استفاده از آرايه • • • • گراف در آراBيه اي بنام Nodeذخيره مي شود. NنBBود گBBBراBفدر اBبتداBيآراBيه BقBBرار ميگBBBيرند شماره نودهاي متصل به نود iام در خانه هاي ]) Node[Node(iتا ])Node[Node(i+1 قرار دارد. اين آرايه چند خانه دارد؟ 0 4 1 3 2 6 8 1 2 1 4 1 8 2 0 1 3 0 2 3 4 1 3 0 1 2 4 1 3 0 1 2 3 4 5 6 7 8 9 1 0 11 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 ليستهاي چند گانه مجاورتي پيمايش گراف • • • • هدف ديدن تمامي نود هاست استفاده از Bساختمان داده استك يا صف پيمايش يا جستجوي عمقي Depth-First-Search )(DFS پيمايش يا جستجوي سطحي Breadth-First-Search )(BFS سواالت • به كمك پيمايشها روشي بيابيد كه متصل بودن گراف BرBا تشخيص دهد. • گراف دو بخشي :چگونه دو بخشي بودن گراف Bرا تشخيص دهيم.