مدل‌ سازی (مسیر و دور و عدد احاطه‌ گری)

تاریخ انتشار: 15 آذر 1399
آخرین ویرایش: 31 شهریور 1400
دسته‌بندی: گراف
امتیاز:
بازدید: 23 مرتبه

گراف‌های Pn و Cn و عدد احاطه‌گری

تعریفPn 

اگر G گرافی از مرتبه n1  با راس‌های زیر باشد:

v1,v2,v3,,vn

اگر این گراف با مجموعه راس‌های فوق برچسب گذاری شده باشند به‌طوری‌که یال‌های آن به‌صورت زیر باشند:

v1v2,v2v3,v3v4,,vn1vn

آن‌گاه گراف G را یک مسیر با n راس Path می‌نامند و با Pn نشان می‌دهند. 

مسیر و دور و عدد احاطه‌گری - پیمان گردلو

عدد احاطه‌گری در گراف Pn به‌صورت زیر محاسبه می‌شود:

γPn=n3

γP1=13=1γP2=23=1γP3=33=1γP4=43=2γP5=53=2γP6=63=2γP7=73=3γP4=83=3

تعریفCn

اگر G گرافی از مرتبه n3  با راس‌های زیر باشد:

v1,v2,v3,,vn

اگر این گراف با مجموعه راس‌های فوق برچسب گذاری شده باشند به‌طوری‌که یال‌های آن به‌صورت زیر باشند:

v1v2,v2v3,v3v4,,vn1vn,vnv1

آن‌گاه گراف G را یک دور با n راس Cycle می‌نامند و با Cn نشان می‌دهند. 

مسیر و دور و عدد احاطه‌گری - پیمان گردلو

عدد احاطه‌گری در گراف Cn به‌صورت زیر محاسبه می‌شود:

γCn=n3

γC3=33=1γC4=43=2γC5=53=2γC6=63=2γC7=73=3

تمرین

گراف‌های زیر را رسم کنید و عدد احاطه‌گری هر یک را مشخص کنید.

P10

مسیر و دور و عدد احاطه‌گری - پیمان گردلو

γP10=103=4


مجموعه احاطه‌گر مینیمم به‌صورت زیر معرفی می‌شود:

v1,v4,v7,v10

P9

مسیر و دور و عدد احاطه‌گری - پیمان گردلو

γP9=93=3


مجموعه احاطه‌گر مینیمم به‌صورت زیر معرفی می‌شود:

v2,v5,v8

C10

مسیر و دور و عدد احاطه‌گری - پیمان گردلو

γC10=103=4


مجموعه احاطه‌گر مینیمم به‌صورت زیر معرفی می‌شود:

v1,v4,v7,v9

C9

مسیر و دور و عدد احاطه‌گری - پیمان گردلو


γC9=93=3


مجموعه احاطه‌گر مینیمم به‌صورت زیر معرفی می‌شود:

v2,v5,v8

P12

مسیر و دور و عدد احاطه‌گری - پیمان گردلو


γGnΔ+1=122+1=4γG4


مجموعه احاطه‌گر مینیمم به‌صورت زیر معرفی می‌شود:

v2,v5,v8,v11γG=4


مسیر و دور و عدد احاطه‌گری - پیمان گردلو


یک مجموعه احاطه‌گر مینیمال6 عضوی از آن را مشخص می‌کنیم:


مسیر و دور و عدد احاطه‌گری - پیمان گردلو


مجموعه زیر یک مجموعه احاطه‌گر مینیمال 6 عضوی است.

v2,v4,v6,v8,v10,v12

تمرین

گرافی مشخص کنید که برای آن،عدد احاطه‌گر برابر nΔ+1 باشد.

مسیر و دور و عدد احاطه‌گری - پیمان گردلو


nΔ+1=92+1=3=3γP9=n3=93=3γP9=nΔ+1

گرافی مشخص کنید که برای آن،عدد احاطه‌گر برابر nΔ+1 نباشد.

مسیر و دور و عدد احاطه‌گری - پیمان گردلو


مجموعه احاطه‌گر مینیمم به‌صورت زیر معرفی می‌شود:

v2,v4,v6,v8,v11


γG=5nΔ+1=113+1=2.75=3γGnΔ+1

برای ارسال نظر وارد سایت شوید