Frucht's theorem
فروچٹ تھیوریم الجبرائی گراف تھیوری میں ایک تھیوریم ہے جس کا قیاس 1936 میں ڈینس کونگ نے کیا تھا اور اسے 1939 میں رابرٹ فروچٹ نے ثابت کیا تھا۔ اس میں کہا گیا ہے کہ ہر محدود گروپ ایک محدود غیر ہدایت شدہ گراف کی ہم آہنگی کا گروپ ہے۔ زیادہ مضبوطی سے، کسی بھی محدود گروپ G کے لیے لامحدود طور پر بہت سے غیر آئسومورفک سادہ جڑے ہوئے گراف موجود ہیں جیسے کہ ان میں سے ہر ایک کا آٹومورفزم گروپ G کے لیے آئسومورفک ہے۔ ثبوت کا بنیادی خیال یہ مشاہدہ کرنا ہے کہ G کا کیلی گراف، G کے جنریٹرز کو ایک دوسرے سے ممتاز کرنے کے لیے اپنے کناروں پر رنگوں اور سمتوں کے اضافے کے ساتھ، مطلوبہ آٹومورفزم گروپ رکھتا ہے۔ لہذا، اگر ان کناروں میں سے ہر ایک کو ایک مناسب ذیلی گراف سے تبدیل کیا جائے، جیسے کہ ہر متبادل ذیلی گراف خود ہی غیر متناسب ہو اور دو متبادل آئسومورفک ہوں اگر اور صرف اس صورت میں جب وہ ایک ہی رنگ کے کناروں کو تبدیل کریں، تو ان تبدیلیوں کو انجام دے کر بنائے گئے غیر ہدایت شدہ گراف میں بھی اس کی ہم آہنگی گروپ کے طور پر G ہوگا۔ گراف کا سائز تین مستثنیات کے ساتھ-ترتیب 3، 4، اور 5 کے چکور گروپ-ہر گروپ کو گراف کی ہم آہنگی کے طور پر پیش کیا جا سکتا ہے جس کے عمودی حصوں میں صرف دو مدار ہوتے ہیں۔ لہذا، گراف میں عمودی حصوں کی تعداد گروپ کی ترتیب سے زیادہ سے زیادہ دوگنی ہوتی ہے۔ مستثنیات کے ایک بڑے سیٹ کے ساتھ، زیادہ تر محدود گروپوں کو ورٹیکس-ٹرانزیکٹو گراف کی ہم آہنگی کے طور پر پیش کیا جا سکتا ہے، جس میں گروپ کی ترتیب کے برابر متعدد عمودی حصے ہوتے ہیں۔ گراف کے خصوصی خاندان فروخت کے نظریہ کے مضبوط ورژن ہیں جو یہ ظاہر کرتے ہیں کہ گراف کے کچھ محدود خاندان اب بھی کسی بھی ہم آہنگی گروپ کا ادراک کرنے کے لیے کافی گراف پر مشتمل ہیں۔ فروچٹ نے ثابت کیا کہ درحقیقت مطلوبہ خاصیت کے ساتھ بہت سے 3-ریگولر گراف موجود ہیں۔ مثال کے طور پر، فروچٹ گراف، 12 عمودی اور 18 کناروں کے ساتھ ایک 3-ریگولر گراف، میں کوئی غیر معمولی ہم آہنگی نہیں ہے، جو معمولی گروپ کے لیے اس قسم کا احساس فراہم کرتا ہے۔ گرٹ صبیدوسی نے دکھایا کہ کسی بھی گروپ کو تمام مثبت عدد اقدار کے لیے (باقاعدہ گرافوں اور کے-کرومیٹک گرافوں کے لیے) شمار کے لحاظ سے بہت سے مختلف کے-ریگولر گراف، کے-ورٹیکس سے منسلک گراف، یا کے-کرومیٹک گراف کے سمیٹری گروپوں کے طور پر محسوس کیا جا سکتا ہے۔ ان حقائق سے کہ ہر گراف کو اس کے کناروں اور عمودی حصوں کی جزوی ترتیب سے دوبارہ تعمیر کیا جا سکتا ہے، کہ ہر محدود جزوی ترتیب برخوف کی نمائندگی تھیوریم کے ذریعہ ایک محدود تقسیم شدہ جالی کے مساوی ہے، اس کے بعد یہ ہوتا ہے کہ ہر محدود گروپ کو تقسیم شدہ جالی کی ہم آہنگی کے طور پر محسوس کیا جا سکتا ہے، اور جالی کے گراف کا، ایک میڈین گراف۔ ہر محدود گروپ کو مضبوط باقاعدہ گراف کی ہم آہنگی کے گروپ کے طور پر محسوس کرنا ممکن ہے۔ ہر محدود گروپ کو نمبر دو میں فرق کرنے والے گراف کی ہم آہنگی کے طور پر بھی محسوس کیا جا سکتا ہے: کوئی بھی (غلط طریقے سے) گراف کو دو رنگوں سے رنگ سکتا ہے تاکہ گراف کی کوئی بھی ہم آہنگی رنگ کو محفوظ نہ رکھے۔ تاہم، گراف کی کچھ اہم کلاسیں تمام گروپوں کو ان کی ہم آہنگی کے طور پر سمجھنے سے قاصر ہیں۔ کیملی جورڈن نے درختوں کے ہم آہنگی گروپوں کو محدود گروپوں کا سب سے چھوٹا مجموعہ قرار دیا جس میں معمولی گروپ ہوتے ہیں اور ایک دوسرے کے ساتھ براہ راست مصنوعات کے تحت بند ہوتے ہیں اور ہم آہنگی گروپوں کے ساتھ پھولوں کی مصنوعات ؛ خاص طور پر، ترتیب تین کا چکور گروپ کسی درخت کا ہم آہنگی گروپ نہیں ہے۔ پلانر گراف بھی تمام گروپوں کو ان کی ہم آہنگی کے طور پر محسوس کرنے کے قابل نہیں ہیں۔ مثال کے طور پر، واحد محدود سادہ گروپ جو پلانر گراف کی ہم آہنگی ہیں وہ چکور گروپ اور متبادل گروپ ہیں۔ زیادہ عام طور پر، ہر معمولی بند گراف خاندان اپنے گراف کی ہم آہنگی کے ذریعے تمام محدود گروپوں کی نمائندگی کرنے کے قابل نہیں ہے۔ لاسزلو بابائی، زیادہ مضبوطی سے، قیاس کرتے ہیں کہ ہر معمولی بند خاندان صرف محدود طور پر بہت سے غیر چکور محدود سادہ گروہوں کی نمائندگی کر سکتا ہے۔ لامحدود گرافوں اور گروپوں ایزبیکی نے 1959 میں ان نتائج کو بڑھایا اور یہ ظاہر کیا کہ کسی بھی محدود ہم آہنگی گروپ کا احساس کرنے والے بے شمار لامحدود گراف موجود ہیں۔ آخر میں، جوہانس ڈی گروٹ اور صبیدوسی نے 1959/1960 میں آزادانہ طور پر ثابت کیا کہ کسی بھی گروپ (اس مفروضے کو چھوڑ کر کہ گروپ محدود ہے، لیکن انتخاب کے محور کے مفروضے کے ساتھ) کو لامحدود گراف کی ہم آہنگی کے گروپ کے طور پر محسوس کیا جا سکتا ہے۔ حوالہ جات ذرائع۔ ۔ ۔ ۔ ۔ ۔ جیسا کہ حوالہ دیا گیا ہے۔ ۔ ۔ الجبرائی گراف تھیوری گراف تھیوری میں نظریات