Slides

Report
‫آمنه فرهادیان‬
‫‪1‬‬
‫‪‬‬
‫‪‬‬
‫‪‬‬
‫‪2‬‬
‫معرفی مسئله‬
‫مروری بر کارهای انجام گرفته‬
‫استفاده از تبدیل فوریه برای حل مشتقی از مسئله‬
‫‪‬‬
‫‪‬‬
‫‪‬‬
‫‪‬‬
‫‪‬‬
‫‪3‬‬
‫صورت ساده و جذاب‬
‫توسط کلی در پایان نامه دکتری درسال ‪1942‬برای درخت ها ثابت کرد‪.‬‬
‫سه سال بعد توسط اوالم‬
‫ایده های مسئله به ‪ 1929‬می رسد‪.‬‬
‫برای گراف های جهت دار و گراف های نامتناهی درست نیست‪.‬‬
4
‫‪‬‬
‫بازسازی ویژگی های گراف‬
‫‪‬‬
‫بازسازی کالس هایی از گراف ها‬
‫◦ تعداد رئوس‪ ،‬تعداد یال ها‪ ،‬دنباله درجات‪...،‬‬
‫◦ اهمیت این کار؟‬
‫◦ درخت ها‪ ،‬گراف های اویلری‪...،‬‬
‫‪5‬‬
‫‪‬‬
‫‪‬‬
‫‪‬‬
‫‪‬‬
‫‪‬‬
‫‪‬‬
‫‪‬‬
‫‪‬‬
‫‪6‬‬
‫تعداد رأس‌ها و یال‌ها‬
‫دنباله درجات گراف‬
‫همبندی گراف‬
‫عدد استقالل و عدد خوشه‌ای‬
‫دنباله درجه همسایه‌های هر رأس‬
‫تعداد یال‌های میان همسایه‌های هر رأس‬
‫چندجمله‌ای رنگی و عدد رنگی‬
‫تعداد زیرگراف‌ها (با شرایط)‬
‫‪‬‬
‫‪‬‬
‫‪‬‬
‫‪‬‬
‫‪‬‬
‫‪‬‬
‫‪7‬‬
‫تعداد دورهای ‌هامیلتونی‬
‫کمر و محیط گراف‬
‫تعداد مسیرهای هامیلتونی‬
‫چندجمله‌ای رنگی و عدد رنگی‬
‫چند جمله‌ای مشخصه گراف‬
‫طیف گراف‬
8
‫‪‬‬
‫‪9‬‬
‫صورت لم کلی مربوط به تعداد زیر گراف های از مرتبه حداکثر‪n-1‬‬
‫است‪ .‬چگونه می توان تعداد دورهای هامیلتونی که زیرگرافی ‪ n‬راس ی است‪،‬‬
‫شمرد؟‬
‫‪‬‬
‫‪‬‬
‫‪‬‬
‫‪‬‬
‫‪‬‬
‫‪‬‬
‫‪10‬‬
‫گراف‌های منتظم‬
‫ی‬
‫گراف‌های اویلر ‌‬
‫گراف‌های ناهمبند‬
‫درخت‌ها‬
‫گراف‌هایی که درجات ممکن برای رأس‌های آن حداقل دو واحد با هم اختالف‬
‫داشته باشند‪.‬‬
‫کالس گراف‌های مسطح قابل تشخیص است و گراف‌های مسطح ماکسیمال‬
‫قابل بازسازی اند‪.‬‬
11
12
‫‪ ‬گراف نامتقار ‌ن‪ :‬گراف ‪ G‬ای که‬
‫‪ ‬تقریبا تمام گراف ها نامتقارن اند‪.‬‬
‫‪13‬‬
‫‪Aut(G)=I‬‬
14
15
‫‪‬‬
‫مسئله بازسازی یالی‬
‫‪‬‬
‫باز سازی گراف سوئچینگ‬
‫◦ توسط هرری در سال ‪1964‬‬
‫◦ حدس‪ :‬هر گراف ساده با حداقل چهار یال قابل بازسازی یالی است‪.‬‬
‫◦ قابل کاهش به مسئله بازسازی راس ی‬
‫◦ توسط استنلی در سال ‪1985‬‬
‫◦ گراف از روی دسته کارتی که از سوئیچ تک تک رئوس بدست آمده است‪ ،‬قابل بازسازی‬
‫است‪.‬‬
‫‪16‬‬
17
‫‪ ‬استنلی ‪:1985‬‬
‫◦ به ازای ‪n‬هایی که بر چهار بخش پذیر نیستند‪ ،‬گراف از روی‬
‫دسته کارت سوئیچ شده قابل بازسازی است‪.‬‬
‫‪18‬‬
19
‫‪‬‬
‫‪‬‬
‫تابع ‪ f‬از ‪ Z2k‬به ‪ R‬است‪.‬‬
‫تبدیل فوریه تابع ‪ f‬به صورت زیر تعریف می شود‪.‬‬
‫تبدیل رادون‌‬
‫‪20‬‬
‫‪‬‬
‫تابع مشخصه ‪Г‬‬
‫‪‬‬
‫بنابراین تبدیل فوریه آن‬
‫‪ ‬لم‪:‬‬
‫تبدیل رادون وارون پذیر است اگر وفقط اگر تبدیل فوریه تابع‬
‫مشخصه ‪ Г‬هرگز صفر نشود‪.‬‬
‫‪21‬‬
22
‫‪‬‬
‫‪‬‬
‫همه گراف های ‪ n‬راس ی برچسب دار‬
‫فضای برداری تمام ترکیبات خطی عناصر باال‬
‫‪ ‬تعریف تابع‬
‫‪23‬‬
‫‪ ‬لم‪:‬‬
‫تابع باال وارون پذیر است اگر و فقط اگر ‪ n‬بر چهار بخش پذیر نباشد‪.‬‬
‫برهان‪:‬‬
‫را به صورت طبیعی با‬
‫متناظر می کنیم‪.‬‬
‫به ازای راس ‪ Ci ،i‬را ستاره ‪ K1,n-1‬با مرکز ‪ xi‬می گیریم‪.‬‬
‫قرار دهید‬
‫تابع ‪f‬‬
‫‪24‬‬
‫‪25‬‬
‫‪‬‬
‫بنابراین‬
‫‪‬‬
‫بنابر لم گفته شده ‪ Ф‬وارون پذیر است اگروفقط اگر‬
‫‪‬‬
‫‪26‬‬
‫گروه تمام جایگشتهای‬
‫عمل می کند‪.‬‬
‫‪‬‬
‫اگر‬
‫‪‬‬
‫اگر‬
‫‪‬‬
‫پس‬
‫که با جایگشت دادن راسها روی‬
‫نگاشت برچسب برداری ‪ f‬را تعریف می کنیم‬
‫‪ ،‬آنگاه‬
‫یک برچسب برداری است‬
‫‪ ‬قضیه‬
‫اگر ‪ n‬بر ‪ 4‬بخشپذیر نباشد‪ ،‬آنگاه گراف از روی دسته کارت سوئیچ شده قابل‬
‫بازسازی است‪ .‬به عبارت دیگر‬
‫برهان‪ :‬داریم‬
‫‪27‬‬
‫‪‬‬
‫قضیه‬
‫برهان‪ :‬داریم‬
‫پس‬
‫‪28‬‬
‫‪‬‬
‫‪‬‬
‫‪‬‬
‫‪29‬‬
‫وقتی ‪ n‬بر ‪ 4‬بخشپذیر نباشد‪ ،‬با توجه به لم قبل خواهیم داشت‬
‫که نتیجه مطلوب است‪.‬‬

similar documents