مقاطع تحصیلی
جستجو در منظومه
کار در کالسٔ درجه سایر ِ رئوس ِ گراف شکل 8 را بنویسید و مشخص کنید کدام رئوس فرد و کدام رئوس زوج اند.بین دو رأس از یک گراف ممکن است ِ بیش از یک یال وجود داشته باشد. همچنینیک یال ممکن است یک رأس را به خود آن رأس وصل نماید که در این صورت بهاین یال طوقه 1 گفته می‌شود. این دو مورد در شکل 10 نمایش داده شده اند. گرافیرا که در آن هیچ یک از این دو مورد اتفاق نیفتاده باشد را گراف ساده می‌گوییم.دیدیم که گراف حاصل از مدل سازی پل کونیگسبرگ یک گراف ساده نیست. ما دراین کتاب فقط گراف های ساده را بررسی خواهیم کرد و از این به بعد منظورمان از شکل 10گراف، گراف ساده است.دو رأس مجاور (همسایه): دو رأس u و v را دو ِ رأس همسایه یا مجاور گوییمهرگاه توسط یالی به هم وصل شده باشند، یعنی (G) ∈E . u v به طور مثال در گرافشکل ،11 رأس v 1 با رئوس v 2 و v 5 همسایه است و رأس v 2 با رئوس v 1 و v 3 و v 4همسایه است.توجه: در زمان رسم نمودار یک گراف توجه داشته باشید که هیچ یالی خودش راقطع نکند و همچنین هیچ یالی نباید از روی رأسی که مربوط به دو سر آن یال نیست شکل 11عبور نماید.مجموعه ٔ همسایه های یک رأس: فرض کنیم V(G) ∈ v ، به ٔ مجموعه رأس ِ هایی از گراف G که به رأس v متصلهستند، «همسایگی باز رأس v » می‌گوییم و با v() N G نمایش می‌دهیم. اضافه ِ کردن خود ِ رأس v به v() N G «همسایگی ٔ بستهرأس v » را به دست می‌دهد که آن را با G N [v] نمایش می‌دهیم. می‌توان این دو مجموعه را به صورت زیر نمایش داد:} E(G(∈ uv : V) G) ∈ u { = v() G N} v { N G [v] = N G(v)به طور مثال در گراف شکل 12 داریم: b} b, a { = c N G(a) = { b } N G [a]} g, d, c, b { = a N G(c) = { b, d, g } N G [c]} f { = N G [f] ∅ = f g N G(f)دو یال مجاور: دو یال را مجاور گوییم هرگاه رأسی وجود داشته باشد که هر دوی آنها e شکل 12به آن متصل باشند. به طور مثال در شکل ،12 یال های bc و cd مجاوراند.Loop 1 ــفصل دوم: گراف و مدل سازی 36