16014

16014

m-رنگ آميزي نام برخي گرافها

كارشناسي ارشد

رياضي - جبر

شهريور 1395

شهريور 1395

دكتر مهدي علائيان

چ ‐رنگ آميزي تام كه وابسته به افراز منصفانه m در اين پايان نامه بعد از بيان مفاهيم بنيادي، مفهوم گراف 􀎈 از ي = fC١; :::;Crg كه افرازي از رئوس مانند 􀍳 كنيم، به اين معن 􀍳 باشد را تعريف م 􀍳 م Cj همسايه در بخش sij دقيقا Ci افراز منصفانه گوييم هرگاه هر راس در 􀎈 را ي G = (VG;EG) كنيم. 􀍳 م 􀍳 اين مفاهيم را روي گراف هاي جانسون و پترسن بررس .i ≠ j داشته باشد، به ازاي منتظم و متقاطر است، تعاريف و قضايايي مهم از اين 􀀀 فاصله 􀍳 از آنجا كه گراف هاي جانسون گراف افراز 􀎈 در منصفانه بودن ي 􀍳 كنيم كه نقش مهم 􀍳 مفاهيم و گراف هاي قويا منتظم بيان و اثبات م دارند. را J(6; ٣); J(٧; ٣) سپس ماتريس هاي پارامتر مربوط به ٢‐رنگ آميزي تام گراف هاي جانسون دهيم. 􀍳 آوريم و در آخر ٣‐رنگ آميزي گراف پترسن را ارائه م 􀍳 بدست م كلمات كليدي: منتظم، گراف قويا منتظم، افراز 􀀀 افراز منصفانه، رنگ آميزي تام، گراف جانسون، گراف فاصله فاصله اي،گراف متقاطر .