"گراف (ریاضی)" کے نسخوں کے درمیان فرق

مثال کے طور پر تصویر 2 میں گھر کا نقشہ دیا ہے۔ اس نقشہ کا گراف بنانے کے لیے ہر کمرے کو راس (دائرہ) سے دکھایا گیا ہے۔ جن دو کمروں کے درمیان دروازہ ہے، گراف میں وہ کنارہ سے جڑے دکھائے گئے ہیں۔ اقماتراس پر کمرے کا عدد لکھا گیا ہے۔ اس طرح یہ کمروں کے اتصال کا گراف ہے۔

[[فائل:Multigraph.svg|تصغیر|125px|بائیں|تصویر 3: گراف کی جامع مثال۔ تین اقماتراس اور چھ کنارے۔]]

تعریف: ''گراف'' ''G'' مشتمل ہوتا ہے غیر خالی مجموعہ پر جس کے ارکان راس ہوتے ہیں اور ان ارکان کے جوڑوں کی نامرتب فہرست پر، جنہیں کنارے کہا جاتا ہے۔ راس کے مجموعہ کو گراف کا "راس مجموعہ" کہتے ہیں اور <code dir="ltr">''V(G)''</code> لکھتے ہیں۔ کناروں کی فہرست کو "کنارہ فہرست" کہتے ہیں اور <code dir="ltr">''E(G)''</code> لکھتے ہیں۔ اگر ''u'' اور ''v'' اقماتراس ہوں، تو کنارہ ''uv'' یا ''vw''، راس ''u'' اور ''v'' کو آپس میں "مِلاتا" ہے۔

* ایسی اقماتراس جن کا درجہ [[طاق عدد]] ہو، کی تعداد جفت عدد ہوتی ہے۔

* باقاعدہ‌گراف درجہ ''r'' کے ساتھ، کی اقماتراس کی تعداد ''n'' ہو، تو کناروں کی تعداد <math>\frac{nr}{2}</math> ہو گی۔

گراف جس میں صرف ایک [[چال (نظریہ گراف)|دورہ]] ہو کو دورہ گراف کہتے ہیں۔ دورہ‌گراف جس کی اقماتراس کی تعداد ''n'' ہو کو <math>C_n</math> لکھتے ہیں۔

گراف جس میں صرف ایک [[رستہ (نظریہ گراف)|رستہ]] ہو کو راستہ‌گراف کہتے ہیں۔ رستہ گراف جس کی اقماتراس کی تعداد ''n'' ہو کو <math>P_n</math> لکھتے ہیں۔

ایسا گراف جس کے راس مجموعہ کو دو ذیلی مجموعات ''A'' اور ''B'' میں بانٹا جا سکے اس طرح کہ ہر کنارہ مجموعہ ''A'' کے کسی قمہ کو مجموعہ ''B'' کے کسی قمہ سے جوڑتا ہو۔ تصویر میں اقماتراس کے ذیلی مجموعات کو "نیلے" اور "سرخ" رنگ میں دکھایا گیا ہے۔

موزون گراف، ایسا گراف جس میں ہر کنارے کے ساتھ ایک مثبت عدد نتھی کر دیا جائے جو اس کا وزن کہلائے۔ مثلاً اگر اقماتراس شہر ہوں تو وزن دو شہروں کے درمیان فاصلہ۔