نطریه ساختار گراف

در ریاضیات، قضیه ساختار گراف (نام علمی: Graph structure theorem) یک نتیجه عمده در زمینه نظریه گراف است. نتیجه برقرار عمیق و اساسی در ارتباط بین نظریه گراف جزئی و برازش گراف است. این قضیه که هفدهمین مقاله از یک سری 23 مقاله‌ای است که توسط نیل رابرتسون و پل سیمور نوشته شده‌است. اثبات آن بسیار طولانی و پیچیده است. (Kawarabayashi و Mohar 2007) و (Lovász 2006) در حال بررسی دسترس به غیر متخصصان، توصیف قضیه و عواقب آن است.

راه اندازی و انگیزه برای قضیه

یک گراف جزئی از گراف آ هر گراف ب است که با گراف هم ریخت است که می‌تواند از یک زیر گراف ب با انقباض چند یال به دست آید. اگر آ شامل گراف ب به عنوان جزئی نباشد، در این صورت می‌گوییم آ ب-آزاد است. فرض کنید آ یک گراف ثابت باشد. به‌طور مستقیم، اگر آ یک گراف عظیم ب-آزاد باشد، در این صورت باید یک "دلیل خوب" برای آن وجود داشته باشد. نظریه ساختار گراف آن "دلیل خوب" را در این شکل توصیف خشن برای ساختار آ را فراهم می‌آورد