فهرست برخی گراف‌های خاص

گراف هی وود یک گراف بدون جهت با14 رأس و 21 یال است .

گراف هی وود ۳-منتظم است و این یعنی از هر راس آن سه یال بیرون آمده است، و همهٔ دورها در آن حداقل 6 و حد اکثر 14 یال دارد . عدد تقاطع گراف 3 است و کوچکترین گراف منتظم با این عدد تقاطع است. این گراف به نام پرسی جان هی وود نامگذاری شده‌است.

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

گراف پترسن یک گراف بدون جهت با ۱۰ رأس و ۱۵ یال است. گرافی کوچک که مثال و مثال نقض مفیدی برای خیلی از مسائل در نظریه گراف است. این گراف به جولیوس پترسن نسبت داده شده ولی در حقیقت برای اولین بار، ۱۲ سال زودتر در سال ۱۸۸۶ به وجود آمده بود.

• نامگذاری به نام: جولیوس پترسن
  تعداد رأس‌ها:10
  تعداد یال‌ها: 15
  قطر:2
  مینیمم طول دور:5
  عدد رنگی:۳
  اندیس رنگی:۴
  منتظم
  غیرمسطح

• عدد تقاطع گراف پترسن 2 است.

• گراف پترسن در صفحه می‌تواند به گونه‌ای رسم شود که طول هر یال برابر واحد باشد

• گراف پترسن شبه هامیلتونی است.

• عدد رنگی گراف پترسن 3 است. یک نمونه رنگ آمیزی با 3 رنگ.

ساخت

گراف پترسن، گراف مکمل گراف خط ${\displaystyle K_5}$

مسیرها و دورهای همیلتونی

گراف پترسن مسیر هامیلتونی دارد ولی دور هامیلتونی ندارد. گراف پترسن کوچکترین گراف شبه هامیلتونی است یعنی اگرچه دور هامیلتونی ندارد، هر کدام از رأس‌هایش که حذف شوند می‌توان یک دور هامیلتونی در آن پیدا کرد.(شکل۴)

در نظریه گراف گراف نسر،${\displaystyle K{G}_{n,k}}$

مثال‌ها

• گراف کامل n رأسی گراف نسر ${\displaystyle K{G}_{n,1}}$
  است.
• گراف ${\displaystyle K{G}_{5,2}}$
  با گراف پترسن ایزومورف است.

خصوصیات

• در گراف نسر هر رأس با انتخاب k از n-k رأس دیگر مجاور است.
• همانگونه که نسر حدس زد عدد رنگی گراف ${\displaystyle K{G}_{n,k}}$
  دقیقاً برابر n-۲k+۲ است. Lovasz در سال ۱۹۷۸ و Joshua در سال ۲۰۰۲ برای این فرمول اثبات‌هایی توپولوژیکی ارائه دادند. در سال ۲۰۰۴ Matoušek اثباتی کاملاً ترکیبیاتی برای آن پیدا کرد.
• وقتی n بزرگتر مساوی ۳k باشد گراف نسر همیشه دور هامیلتونی خواهد داشت (چن ۲۰۰۰). محاسبات نشان داده‌اند که همهٔ گراف‌های همبند کنزر با n‌های کوچکتر مساوی ۲۷ به جز گراف پترسن، همیلتونی هستند.
• اگر n کوچکتر از ۳k باشد گراف نسر هیچ مثلثی نخواهد داشت.

مکعب‌ها با ابعاد مختلف می‌توانند گراف در نظر گرفته شوند. مکعب با بعد n را با ${\displaystyle Q_n}$

درخت زندگی سمبل اصلی آئین کابالا است. در شکل رأس‌ها، ۱۰ سفیروت (مظهر خدایی) را نمایش می‌دهند(به عقیدهٔ Zohar، جهان در ده کلمه خلق شده‌است). ۲۲ یال(برابر ۲۲ تا حرف عبری کانال‌هایی هستند که نیروهای یزدانی از نیان آن‌ها عبور می‌کنند.) این شکل به‌طور عمده بدنهٔ جهان یا نقشه خلقت را نشان می‌دهد.

هر مازی نظیر یک گراف است. رأس‌ها را محل‌های تقاطع راه‌ها، و یال‌ها را معادل مسیرها در نظر می‌گیریم. قدیمی‌ترین ماز باقی مانده در بریتانیا در قصر همپتون قرار دارد. قابلیت عبور از مازها یک زمانی مسئلهٔ مهمی بود. سؤال این است که آیا الگوریتمی وجود دارد که کسی بتواند بدون آنکه از قبل ساختار ماز را بداند، از ماز عبور کند و از هر مسیر دو بار در جهت مخالف عبور کند؟ اولین الگوریتم برای عبور از یک ماز به C.Wiener نسبت داده شده‌است. Tremaux الگوریتمی بهینه تر در سال ۱۸۸۲ ارائه داد. ساده‌ترین و بهترین الگوریتم را Tarry در سال ۱۸۹۵ پیشنهاد داد.

• Graphs we live by
• en:Kneser_graph
• en:Petersen_Graph
• en:Heawood_graph