جامع ترین آموزش درباره ی گراف همه ی نکات گراف در یکجا

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

تعریف گراف و راس، یال، اندازه، همسایه

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

مجموعه راس های $( Vertex)$ گراف را با $V(G)$ و تعداد راس های گراف را با $n(V(G))$ یا $|V(G) |$ نشان می دهند.

مجموعه یال های $( Edge)$ گراف را با $E(G)$ و تعداد یال های گراف را با $n(E(G))$ یا $|E(G)|$ نشان می دهند.

نکته: مجموعه راس های گراف همواره ناتهی در نظر گرفته می شود.

توجه: برای رسم نمودار یک گراف یا شکل گراف روش یکتایی مدنظر نیست. آنچه مهم است این است که باید مشخص باشد که گراف مورد نظر چند رأس و چند یال دارد و کدام یال به کدام رئوس متصل است.

تعریف: یال طوقه $loop$ یالی است که یک راس را به خودش وصل می کند.

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

مرتبه و اندازه گراف

به تعداد راس های گراف مرتبه گراف می گویند. و با $p(G)$ نشان می دهند. تعداد یال های گراف را اندازه گراف می گویند و با $q(G)$ نمایش می دهیم.

درجه یک راس

درجه راس $v$ در گراف $G$ برابر است با تعداد یال هایی از گراف $G$ که به راس $v$ متصل اند و آن را با $\deg_{G}(v)$ یا به طور ساده تر $\deg(v)$ یا $d(v)$ نمایش می دهیم . اگر درجه راس فرد باشد آن را راس فرد و اگر درجه راس زوج باشد آن را راس زوج می نامیم.

راس تنها : به راسی که درجه آن صفر باشد یعنی هیچ یالی به آن متصل نباشد راس تنها یا ایزوله می گوییم.

دو راس مجاور یا همسایه

دو راس $u$ و $v$ را دو راس همسایه یا مجاور گوییم هرگاه توسط یالی یه هم وصل شده باشند یعنی $uv \in E(G)$

مجموعه همسایه های یک راس

فرض کنیم $v \in V(G)$ ، به مجموعه راس هایی از گراف $G$ که به راس $v$ متصل هستند همسایگی باز راس $v$ می گوییم و با $N_{G}(v)$ نمایش می دهیم. اضافه کردن خود راس $v$ به $N_{G}(v)$ همسایگی بسته راس $v$ را بدست می دهد که آن را با $N_{G}[v]$ نمایش می دهیم.

می توان این دو مجموعه را به صورت زیر نمایش داد:

$N_{G}(v)=\{u \in V(G):uv \in E(G)\}$

$N_{G}[v]=N_{G}(v)\cup \{v\}$

دو یال مجاور

دو یال را مجاور گوییم هرگاه راسی وجود داشته باشد که هر دوی آن ها به آن متصل باشند.

بزرگترین و کوچکترین درجه یک گراف

بزرگترین عدد در بین درجات رئوس گراف $G$ را با $\Delta(G)$ و کوچکترین آن ها را با $\delta(G)$ نمایش می دهیم و به ترتیب آن ها را ماکزیمم و مینیمم درجه گراف می نامیم.

زیرگراف

یک زیرگراف از گراف $G$ گرافی است که مجموعه رئوس آن زیرمجموعه ای از مجموعه رئوس گراف $G$ و مجموعه یال های آن زیرمجموعه ای از مجموعه یال های $G$ باشد.

مکمل یک گراف

مکمل گرافی مانند $G$ که آن را با $G^{c}$ یا $\overline{G}$ نمایش می دهیم گرافی است که مجموعه رئوس آن همان مجموعه رئوس گراف $G$ است و بین دو راس از $G^{c}$ یک یال است اگر و تنها اگر بین همان دو راس در $G$ یالی وجود نداشته باشد.

مسیر

اگر $u$ و $v$ دو راس از گراف $G$ باشند کی مسیر از $u$ به $v$ (یک $u-v$ مسیر) در $G$ دنباله ای از رئوس دو به دو متمایز در $G$ است که از $u$ شروع و به $v$ ختم می شود به طوری که هر دو راس متوالی این دنباله در $G$ مجاور هم باشند. طول یک مسیر برابر است با تعداد یال های موجود در آن مسیر (یکی کمتر از تعداد رئوس موجود در آن مسیر) قرار داد می کنیم که دنباله ی متشکل زا تنها یک راس $v$ ، یک مسیر است با طول صفر از راس $v$ به خودش.

گرافی که تنها از مسیر $n$ راسی تشکیل شده باشد با $P_{n}$ نمایش می دهیم.

دور: دنباله $v_{1}v_{2}v_{3}…v_{n}v_{1}\,\,\,n \ge 3$ از رئوس دو به دو متمایز که در آن هر راس با راس بعدی مجاور است را یک دور به طول $n$ می نامیم.

گرافی که تنها از یک دور $n$ راسی تشکیل شده باشد را با $C_{n}$ نمایش می دهیم.

انواع گراف

در این بخش چند نوع گراف را معرفی می کنیم:

گراف جهت دار

به گرافی که برای یال های آن جهت تعیین شده باشد، گراف جهت دار می گوییم. در این حالت برای نمایش اینکه جهت یک یال از سمت کدام رأس به سمت کدام رأس است یال ها را با زوج مرتب نشان می دهیم.

گراف k-منتظم

گرافی را که درجه تمام رئوس آن با هم مساوی و برابر با عدد $k$ باشند گراف $k$ منتطم می نامیم.

گراف تهی

گرافی که تمام رئوس آن راس تنها باشند یعنی هیچ یالی نداشته باشد گراف تهی می نامیم بنابراین منظور از گراف تهی $n$ راسی گرافی شامل $n$ راس تنها و بدون یال است.

گراف ساده

گراف ساده گرافی است که بین دو راس بیش از یک یال وجود ندارد و همچنین گراف دارای یال طوقه نیست.

گراف کامل

گرافی را که هر راس آن با تمام رئوس دیگر مجاور باشد گراف کامل می نامیم گراف کامل $n$ راسی را با $k_{n}$ نمایش می دهیم. می توان گفت $k_{n}$ یک گراف $n$ راسی و $n-1$ منتظم است.

گراف همبند و ناهمبند

گراف $G$ را همبند می نامیم هرگاه بین هر دو راس آن حداقل یک مسیر وجود داشته باشد در غیر این صورت آن را ناهمبند می نامیم.

قضیه : اگر $G$ یک گراف با مرتبه $p$ و اندازه $q$ و $V=\{v_{1},v_{2},…v_{n}\}$ مجموعه رئوس آن باشند آنگاه:

$\sum_{i=1}^{p}\deg v_{i}=2q$

نتیجه : تعداد راس های مجموعه هر گراف عددی زوج است.

مجموعه احاطه گر چیست؟

تعریف : زیرمجموعه $D$ از مجموعه رئوس گراف $G$ را مجموعه احاطه گر می نامیم هرگاه هر راس از گراف یا در $D$ باشد و یا حداقل با یکی از رئوس $D$ مجاور باشد.

یک گراف می تواند مجموعه های احاطه گر گوناگونی داشته باشد. از طرفی واضح است که هر مجموعه که شامل یک مجموعه احاطه گر باشد، احاطه گر است. در بین تمام مجموعه های احاطه گر یک گراف، مجموعه ای را که کمترین تعداد عضو را داشته باشد مجموعۀ احاطه گر مینیمم آن گراف می نامیم.

تعریف : در بین تمام مجموعه های احاطه گر گراف $G$ مجموعه یا مجموعه های احاطه گری که کمترین تعداد عضو را دارند مجموعه احاطه گر مینیمم و تعداد اعضای چنین مجموعه ای را عدد احاطه گری گراف $G$ می نامیم و آن را با $\gamma(G)$ نمایش می دهیم.

گاهی اوقات برای راحتی به یک مجموعه احاطه گر مینیمم از گراف $G$ یک $\gamma$ مجموعه می گوییم.

عدد احاطه گری یک گراف ناهمبند با جمع بدست می آید اما برای گرافق همبند باید محاسبه انجام داد.

تعریف: یک مجموعه احاطه گر را که با حذف هر یک از راس هایش دیگر احاطه گر نباشد احاطه گر مینیمال می گویند.

معرفی یک نماد: اگر $x$ یک عدد غیر صحیح باشد به بزرگترین عدد صحیح قبل از $x$ ، جز صحیح $x$ می گویند که با نماد $[x]$ نشان داده می شود و به کوچکترین عدد صحیح بعد از $x$ سقف $x$ می گویند و با $\lceil x\rceil$ نشان می دهند.

نکته : اگر $G$ یک گراف $n$ راسی با ماکزیمم درجه $\Delta$ باشد و $D$ یک مجموعه احاطه گر در آن باشد آنگاه $\lceil \frac{n}{\Delta+1} \rceil \le |D|$ و از آنجا که $\gamma (G)$ نیز اندازه یک مجموعه احاطه گر است همواره داریم $\lceil \frac{n}{\Delta+1} \rceil \le \gamma(G)$ (اصطلاحا گفته می شود در گراف $G$ عدد $\lceil \frac{n}{\Delta+1} \rceil$ یک کران پایین است برای $\gamma(G)$ یعنی $\gamma(G)$ نمی تواند از آن کمتر شود).

جمع بندی

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

جامع ترین آموزش درباره ی گراف همه ی نکات گراف در یکجا

تعریف گراف و راس، یال، اندازه، همسایه

انواع گراف

مجموعه احاطه گر چیست؟

دیدگاهتان را بنویسید لغو پاسخ

آخرین مطالب وبلاگ

دنباله های عددی

تابع خطی و معادله خط

تابع و دامنه و برد آن

تعیین علامت

عبارت و معادله گویا

معادله درجه دوم

معادله

عبارت جبری

قدرمطلق

دوره ها

دسترسی سریع

دسترسی سریع

مقالات مادر