نمودار پیترسن

نمودار, پیترسن,
نمودار, كلاسيك نمودار, پيترسن ، به شكل يك پنتاگون متمركز و پنتاگرام كه ​​به وسيله پنج پرتو متصل مي شود.
تعداد اجلاس	10
تعداد لبه ها	15
توزیع درجه	3- منظم
اشعه	2
قطر	2
کوک	5
automorphisms	120 ( اس 5 )
شماره کروماتیک	3
فهرست کروماتیک	4
خواص	قفس مکعب فاصله-متعدی از راه دور واحد به طور منظم به شدت Hypohamiltonien نمودار, مور گزارش روز متقارن
تغییر

گراف پترسن است، در نظریه گراف ، یک گراف خاص با 10 راس و 15 لبه.

این یک نمودار, کوچک است که به عنوان نمونه و نمونه ای از شمارش معکوس برای چندین مشکل در تئوری نمودار, ارائه می شود. این است که پس از نام ریاضیدان جولیوس پترسن که در سال 1898 به عنوان کوچکترین معرفی نمودار, مکعب بدون تنگه که لبه می تواند رنگی با سه رنگ 1 . اما این مورد توسط آلفرد کمپ برای اولین بار در 12 سال پیش ، در سال 1886 ذکر شده است 2 .

دونالد کنوت توضیح می دهد در هنر برنامه نویسی کامپیوتر که گراف پترسن است "یک الگوی قابل توجه است که در برابر-به عنوان مثال برای بسیاری از پیش بینی های خوش بینانه در مورد آنچه که باید برای همه گرافها درست باشد در خدمت 3  " .

خلاصه

• 1ساخت و ساز
• 2ویژگی
  • 2.1ویژگی های عمومی
  • 2.2غواصی
  • 2.3خاصیت جبری
  • 2.4مسیرها و چرخه های همیلتون
  • 2.5رنگ آمیزی
• 3یادداشت و منابع
• 4همچنین ببینید
  • 4.1مقالات مرتبط
  • 4.2لینک های خارجی

ساخت و ساز [ تغییر | تغییر کد ]

گراف پترسن است مکمل از نمودار, خط از گراف کامل { نمایشگر K_ {5}}. این نیز نمودار, Kneser است { نمایشگر KG_ {5،2}} ؛ بنابراین می توان با در نظر گرفتن یک راس برای هر جفت از یک مجموعه از 5 عنصر ، و ایجاد یک راس در صورت جدا شدن جفت های مربوطه ، نمودار, گرافیک پیترسن, را ساخت.

از نظر هندسی ، نمودار پیترسن, گرافی است که توسط رئوس و لبه های hemi - dodecahedron  (en) ، یک dodecahedron تشکیل شده است که عمودها ، لبه ها و چهره های مخالف آن به صورت جفت مشخص می شود.

خصوصیات [ ویرایش | تغییر کد ]

خصوصیات عمومی [ ویرایش | تغییر کد ]

نمودار پیترسن, گرافی از مور است. هر مسیر عرض (D-1) من قله به آن من هفتم سطح.

نمودار پیترسن, قفس (3،5) است ، به این معنی که می توان نمودارهای حداقل را در تعداد قائم با مش 5 و مکعب بیان کرد . این قفس تنها (3،5) است و اندازه آن همزمان با مور محدود است ، محدودیتی پایین تر بر روی تعداد راس هایی که یک قفس می تواند داشته باشد. چنین گرافیکی را مور مور می نامند .

قطر از گراف پترسن، حداکثر خروج از مرکز از قله آن و آن شعاع ، حداقل خروج از مرکز آن راس، به 2. برابر هستند این باعث می شود تمام رئوس متعلق به مرکز. همچنین بزرگترین نمودار مکعب با قطر 2 است.

نمودار پیترسن, دارای 3 محور اتصال و 3- لبه متصل است ، یعنی بهم متصل است و برای قطع اتصال آن باید از حداقل 3 راس یا 3 لبه محروم شود. همانطور که مرتبا از درجه 3 است ، این تعداد بهینه است. بنابراین نمودار پیترسن, یک نمودار بهینه متصل است.

نمودار پیترسن, دارای 2000 درخت پوشاننده است که حداکثر در بین نمودارهای مکعب با 10 راس 4 ، 5 است .

غواصی [ ویرایش | تغییر کد ]

نمودار پیترسن, مسطح نیست . هر گراف غیر مسطح است به عنوان جزئی است گراف کامل ، نمودار کامل دو طرفه  ؛ نمودار پیترسن هر دو را دارد.

رایج ترین نقشه هواپیما نمودار پیترسن را به شکل پنتاگرام موجود در یک پنج ضلعی طراحی می کند و دارای پنج تقاطع است. این نقاشی تعداد صلیب ها  (در) را به حداقل نمی رساند  . نمایانگر نمودار پیستن تنها با دو تقاطع امکان پذیر است. در یک توروس ، نمودار پیترسن می تواند بدون عبور نشان داده شود. بنابراین یک نمودار گشتاور است و نوع آن برابر با 1 است.

ساده ترین سطح غیر جهت گیری که بر روی آن می توان نمودار پیستن را بدون عبور از آن گرفتار کرد ، هواپیمای پروژکتور است . این تعبیه توسط ساخت و ساز از hemi-dodecahedron داده می شود.

نمودار پیستن نیز یک نمودار واحد فاصله است  : می توان از طریق مجموعه ای از نقاط هواپیمای اقلیدسی با اتصال به یک لبه ، همه جفت های نقاط را از فاصله 1 به دست آورد. در چنین نمایشی ، چندین لبه تقاطع دارند.

خصوصیات جبری [ ویرایش | تغییر کد ]

نمودار پیترسن بسیار منظم است . همچنین متقارن است ، به این معنی که گروه اتومبیل های آن به صورت انتقالی بر روی لبه ها ، رئوسها و قوس های آن عمل می کنند. بنابراین همچنین دارای لبه گذرا و روبشی است . نمودار پیترسن تنها نمودار مکعبی 10- محوره مکعب متقارن است و نشانه آن در سرشماری فاستر ، کاتالوگ طبقه بندی کلیه نمودارهای مکعب متقارن ، F10A 6 ، 7 است .

این گروه از automorphisms از گراف پترسن است گروه متقارن  ؛ یک گروه از دستور 120. عمل از در نمودار پیترسن از ساخت آن به عنوان یک نمودار کنزر مشتق شده است . هر همریخت از گراف پترسن در خود که راس مجاور شناسایی یک های automorphism است. بازنمایی مسطح نمودار پیترسن نمی تواند کل گروه متقارن آن را نمایندگی کند.

علیرغم تقارن زیاد ، نمودار پیترسن گرافی از کایلی نیست ، کوچکترین نمودار انتقال گره ای است.

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

مسیرها و چرخه های همیلتون [ ویرایش | تغییر کد ]

نمایندگی برجسته از هیپوهامیلتی بودن نمودار پیترسن.

نمودار پیترسن دارای 240 مسیر همیلتون مجزا است اما همیلتون نیست ، بنابراین چرخه همیلتون را ندارد. این کوچکترین نمودار مکعب بدون isthmus نیست که همیلتون باشد. همچنین hypohamiltonian است ، به این معنی که سرکوب هر راس از نمودار پیترسن کافی است تا آن را همیلتونیایی کند. این کوچکترین نمودار هیپوهیلتونی 8 ، 9 است .

به عنوان یک گراف همبند به پایان رسید بالا متعدی و غیر هامیلتونی، آن را ارائه می دهد در برابر-به عنوان مثال برای یک نوع از این حدس از Lovász  (در) که می گوید تمام نمودار بالا متعدی هستند هامیلتونی. اما تدوین کانونی حدس فقط به یک مسیر همیلتون نیاز دارد و بنابراین توسط نمودار پیترسن تأیید می شود.

فقط پنج نمودار به پایان رسیده vertex-transitive و non-Hamiltonian شناخته شده است: نمودار کامل K 2 ، نمودار Peteren ، نمودار Coxeter و دو نمودار به دست آمده از نمودار Petersen و نمودار Coxeter ، و جایگزین هر راس با یک مثلث 7 .

اگر یک گراف است 2 متصل، R -régulier تا 3 R  + 1 راس، پس از آن G هامیلتونی است یا G گراف پترسن است 1 .

برای اثبات اینكه نمودار پیترسن چرخه C همیلتون را قبول ندارد می توان با توصیف نمودارهای 3 معمولی همیلتون و با اثبات اینكه هیچكدام از آنها نمودار پیستن نیستند زیرا همه آنها از 5 مش كمتر خواهند بود. هر نمودار مکعبی ده گوشه ای همیلتون شامل یک سیکل C و پنج بند است . اگر یک رشته دو راس که به دور دو یا سه در چرخه C قرار دارند متصل شود ، نمودار مورد نظر یک چرخه 3 یا 4 چرخه را می پذیرد. اگر دو رشته دو شاخه مخالف را در C به رأسهایی متصل كنند كه هر دو با فاصله 4 باشند ، باز هم یک چرخه 4 وجود دارد. تنها مورد باقیمانده مقیاس مبیوس استنمودار با اتصال هر راس C به راس مقابل (یعنی با فاصله 5) تشکیل شده است. اما مقیاس Möbius همچنین یک چرخه 4 چرخه را تصدیق می کند. نمودار پیترسن از مش 5 است ، یعنی می گویند طول چرخه کوتاهتر آن 5 است. در نتیجه همیلتون نیست

رنگ آمیزی [ ویرایش | تغییر کد ]

4 رنگ لبه های نمودار پیترسن.

3 رنگی از رئوسهای نمودار پیترسن.

عدد رنگی گراف پترسن 3. این است که می گویند، ممکن است به رنگ راس را با 3 رنگ، به طوری که دو راس از یک یال از رنگ های مختلف متصل می شود. این تعداد حداقل است. 3-رنگ شکل مقابل یک رنگ آمیزی منصفانه است ، جایی که سه رنگ تقریباً به همان اندازه نشان داده شده است.

شاخص رنگی از گراف پترسن 4. است بنابراین-4-رنگ آمیزی از یالهای گراف به طوری که دو لبه حادثه را به راس همان همیشه رنگ متفاوت وجود دارد. این تعداد حداقل است. نمودار پیترسن یک جرقه است ، یک نمودار متصل ، بدون ایسموس ، مکعب ، حداقل 5 مش و شاخص کروماتیک 4. این کوچکترین جرقه ممکن است و این تنها جرقه ای بود که از 1898 تا 1946 شناخته شده است. ، تا اینکه Danilo Blanuša دو نمونه دیگر را به نمایش می گذارد ، اولین جرقه Blanuša و دیگری Blanuša 10 snark .

قضیه از گزارش روز ، در نتیجه حدس زده شده توسط WT Tutte و ثابت در سال 2001 توسط رابرتسون، سندرز، سیمور و توماس می گوید که هر گزارش روز اذعان می کند گراف پترسن به عنوان یک جزئی 11 .

می توان رنگهای مختلف نمودار پیترسن را شمارش کرد. این بسته به تعداد رنگ مجاز ، یک عملکرد را می دهد. این یک تابع چند جملهای است و چند جملهای مرتبط با آن ، چند جملهای کرومیک نامیده می شود . این چند جملهای درجه 10 برای ریشه همه اعداد صحیح مثبت یا تهی را کاملاً پایین قرار می دهد. برابر است با:.

نمودار دارای نمودار کروماتیکی کسری 3 است ، نشان می دهد که اختلاف بین شاخص کرومی و شاخص کروماتیکی کسری یک نمودار می تواند برابر با 1 باشد. حدس گلدبرگ-سیمور فرض می کند که این بزرگترین تفاوت ممکن.

تعداد Thue به  (FA) (یک تنوع از شاخص رنگی) از گراف پترسن به 5 برابر است.