سرفصل‌های این مبحث

گراف

مدل‌ سازی (عدد احاطه‌ گری)

آخرین ویرایش: 14 شهریور 1403

دسته‌بندی: گراف

امتیاز:

نظر کاربران: برای نظر دادن اولین باش!

پیدا کردن مجموعه احاطه‌گر ماکزیمم جذابیتی ندارد، زیرا خود $V$ به‌عنوان مجموعه رئوس یگ گراف، یک مجموعه احاطه‌گرِ خودش است که بیشترین تعداد عضو را دارد اما مجموعه احاطه‌گر مینیمم مهم است.

تمرین

گراف زیر را در نظر بگیرید:

عدد احاطه‌گری - پیمان گردلو

برای $G$ مجموعه‌های احاطه‌گری پیدا کنید.

مجموعه $\{b, e, y, u\}$ یک زیرمجموعه $V$ است که یک مجموعه احاطه‌گر برای $G$ با چهار عضو محسوب می‌شود.

مجموعه $\{b, v, x, y\}$ یک زیرمجموعه $V$ است که یک مجموعه احاطه‌گر برای $G$ با چهار عضو محسوب می‌شود.

آیا می‌توان یک مجموعه احاطه‌گر با تعداد عضو کمتر برای $G$ پیدا کرد؟

با کمی دقت مشاهده می‌کنید که $\{a, v, x\}$ یک مجموعه احاطه‌گر سه‌عضوی برای گراف $G$ است.

آیا می‌توان یک مجموعه احاطه‌گری با کمتر از سه‌عضو برای $G$ پیدا کنید؟

فرض کنیم بتوان گراف $G$ را با یک مجموعه دوعضوی از راس‌های $V$ احاطه کرد، این دو راس را $p$ و $q$ بنامیم.

راس $p$ خودش و رئوس مجاور خود را احاطه می‌کند، به‌عبارتی راس $p$ تعداد $1 + \deg (p)$ راس را احاطه می‌کند.

راس $q$ خودش و رئوس مجاور خود را احاطه می‌کند، به‌عبارتی راس $q$ تعداد $1 + \deg (q)$ راس را احاطه می‌کند.

پس این دو راس حداکثر به تعداد زیر می‌توانند رئوس گراف $G$ را احاطه کنند:

$1 + \deg (p) + 1 + \deg (q) = 2 + \deg (p) + \deg (q)$

اما ماکزیمم درجه در این گراف $Δ (G) = 4$ است، پس:

$2 + \deg (p) + \deg (q) \leq 2 + 4 + 4 = 10$

پس حداکثر این دو راس می‌توانند $10$ راس از رئوس گراف $G$ را احاطه کنند.

اما گراف $G$ از مرتبه $11$ است، در نتیجه لااقل یک راس آن به‌وسیله هیچ راسی از $G$ احاطه نمی‌شود پس با هیچ مجموعه دوعضوی از راس‌های $G$ نمی‌توان این گراف را احاطه کرد.

در نتیجه می‌گوییم، $\{a, v, x\}$ یک مجموعه احاطه‌گر با کم‌ترین عضو یا مینیمم برای گراف $G$ است.

تعریف عدد احاطه‌گری

در بین تمام مجموعه‌های احاطه‌گرِ گراف $G$ مجموعه یا مجموعه‌های احاطه‌گری که کمترین تعداد عضو را دارند، مجموعه احاطه‌گر مینیمم نامیده می‌شوند و تعداد اعضای چنین مجموعه‌ای را عدد احاطه‌گری گراف $G$ می‌نامیم و آن را با $γ (G)$ نمایش می‌دهیم.

تمرین

گراف زیر را با دور $C_{7}$ در نظر بگیرید:

عدد احاطه‌گری - پیمان گردلو

عدد احاطه‌گری گراف $G$ را به‌دست آورید.

مجموعه‌های $\{\begin{cases} \{v_{1}, v_{4}, v_{6}\} \\ \{v_{2}, v_{5}, v_{7}\} \end{cases}$ مجموعه‌های احاطه‌گر مینیمم می‌باشد.

با کمتر از سه راس، نمی‌توانیم رئوس دیگرِ گراف را احاطه کنیم، بنابراین عدد احاطه‌گری گراف $G$ به‌صورت زیر است:

$γ (G) = 3$

تمرین

یک شبکه کامپیوتری شامل $16$ کامپیوتر را در نظر بگیرید که در آن هر کامپیوتر مطابق شکل زیر به چند کامپیوترِ دیگر متصل است.

عدد احاطه‌گری - پیمان گردلو

گراف فوق یک مدل‌سازی از شبکه مورد نظر است که در آن هر راس نشان دهنده یک کامپیوتر و یال بین دو راس نشان دهنده آن است که کامپیوترهای نظیر به آن دو راس مستقیما با هم در ارتباط هستند.

مجموعه‌ای با کمترین تعداد ممکن از کامپیوترها (راس‌ها) انتخاب کنید به‌طوری‌که توسط این مجموعه از کامپیوترها به تمام کامپیوترهای این شبکه وصل باشیم.

$\{p, k, b, e\}$ مجموعه انتخاب شده از رئوس برای گراف مورد نظر یک مجموعه احاطه‌گر مینیمم است.

عدد احاطه‌گری - پیمان گردلو

نکته

1- برای راحتی، به یک مجموعه احاطه‌گرِ مینیمم از گرافِ $G$ ، (یک $- γ$ مجموعه) می‌گوییم.

تمرین

گراف زیر را در نظر بگیرید:

عدد احاطه‌گری - پیمان گردلو

دو مجموعه احاطه‌گر مینیمم، معرفی کنید.

مجموعه‌های دو‌عضوی $\{\begin{cases} \{c, e\} \\ \{e, d\} \end{cases}$ دو مجموعه احاطه‌گر مینیمم یا اصطلاحا (دو $- γ$ مجموعه) هستند.

$γ (G) = 2$

تمرین

یک گراف شش راسی که ( $- γ$ مجموعه) آن با اندازه یک باشد را رسم کنید.

عدد احاطه‌گری - پیمان گردلو

مجموعه $\{v_{1}\}$ یک مجموعه احاطه‌گری است، پس عدد احاطه‌گری آن $γ (G) = 1$ است.

یک گراف شش راسی که ( $- γ$ مجموعه) آن با اندازه دو باشد را رسم کنید.

عدد احاطه‌گری - پیمان گردلو

مجموعه $\{v_{1}, v_{2}\}$ یک مجموعه احاطه‌گری است، پس عدد احاطه‌گری آن $γ (G) = 2$ است.

نکته

2- عدد احاطه‌گری یک گراف ناهمبند به‌سادگی و با استفاده از یک عمل جمع ساده به‌دست می‌آید، در این بخش احاطه‌گری گراف‌های همبند مد نظر است.

3- چون مجموعه راس‌های یک گراف همواره یک مجموعه احاطه‌گر خودش است، برای هر گراف عدد احاطه‌گری تعریف می‌شود.

4- گراف تهی، گراف بدون یال است، به‌عبارت دیگر گراف ( $- 0$ منتظم) از مرتبه $n$ و بدون یال است و با $k_{n}$ نمایش می‌دهیم.

در این‌صورت $V (G)$ تنها مجموعه احاطه‌گر $G$ است که مینیمم نیز به‌حساب می‌آید، یعنی در گراف از مرتبه $n$ داریم $γ (G) = n$ اگر و فقط اگر $G$ گراف $k_{n}$ باشد.

5- یک گراف $G$ از مرتبه $n$ دارای عدد احاطه‌گری $(1)$ است، اگر و فقط اگر $G$ شامل یک راس $v$ از درجه $n - 1$ باشد.

$γ (G) = 1 \Leftrightarrow \deg (v) = n - 1$

در این حالت $\{v\}$ یک مجموعه احاطه‌گر مینیمم است.

عدد احاطه‌گری - پیمان گردلو

در گراف فوق داریم:

اگر $γ (G) = 1$ باشد، یک راس با ماکزیمم درجه وجود دارد.

فرض کنیم گراف فوق $n$ راسی باشد. از ویژگی‌های این گراف آن است که حداقل $n - 1$ یال موجود است و در این وضعیت داریم:

$Δ (G) = n - 1$

حداکثر تعداد یال‌ها:

$(\begin{array}{l} n \\ 2 \end{array}) = \frac{n (n - 1)}{2}$

و در این وضعیت داریم:

$Δ (G) = n - 1$

6- در هر گراف کامل، هر راس می‌تواند یک مجموعه احاطه‌گر گراف باشد زیرا هر راس به راس دیگر متصل است.

بنابراین در هر گراف کامل، مجموعه احاطه‌گر مینیمم فقط یک عضودارد یعنی $n - 1$ عدد احاطه‌گری برابر $1$ است.

عدد احاطه‌گری - پیمان گردلو

اما عکس آن همواره درست نیست، زیرا در هر گرافی از مرتبه $n$ که درجه راس آن $n - 1$ باشد، داریم:

$γ (G) = 1$

عدد احاطه‌گری - پیمان گردلو

اگر $γ (G) = 1$ باشد، گراف $G$ حداقل یک راس از درجه $n - 1$ دارد پس می‌تواند از $n - 1$ یال تا $\frac{n (n - 1)}{2}$ یال وقتی گراف کامل است، داشته باشد.

7- اگر $G$ گرافی از مرتبه $n$ باشد، آن‌گاه:

$1 \leq γ (G) \leq n$

یادآوری

تابع کف و تابع سقف

تابع $\{\begin{cases} f : ℝ \to ℤ \\ f (x) = ⌊x⌋ \end{cases}$ را تابع جزء‌صحیح یا تابع کف می‌نامیم و به‌صورت زیر تعریف می‌شود:

$i f ⌊x⌋ = n \Leftrightarrow n \leq x < n + 1$

$f (x) = ⌊x⌋$ یک تابع پله ای است که مقدار آن در هر یک از فواصل $[n, n + 1)$ مقداری ثابت است.

یکی از مهم‌ترین توابع پله ای، تابع جزء‌صحیح یا براکت (کف) است، که معمولا به‌جای $⌊x⌋$ از نماد $[x]$ استفاده می‌شود.

تابع $\{\begin{cases} f : ℝ \to ℤ \\ f (x) = ⌈x⌉ \end{cases}$ را تابع سقف می‌نامیم و به‌صورت زیر تعریف می‌شود.

$i f ⌈x⌉ = n \Leftrightarrow n < x \leq n + 1$

$f (x) = ⌈x⌉$ یک تابع پله ای است که مقدار آن در هر یک از فواصل $(n, n + 1]$ ثابت است.

معمولا در ریاضیات وقتی صحبت از براکت است منظور همان تابع کف است، که $⌊x⌋$ به‌صورت $[x]$ نمایش داده می‌شود نه تابع سقف $⌈x⌉$ .

قضیه

اگر $G$ گرافی از مرتبه $n$ و $δ (G) \geq 1$ ، آن‌گاه:

$δ (G) \leq ⌊\frac{n}{2}⌋$

اثبات

اگر $D$ یک مجموعه احاطه‌گر مینیمال برای گراف $G$ باشد که $δ (G) \geq 1$ آن‌گاه $V - D$ نیز یک مجموعه احاطه‌گر $G$ است.

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

$|V - D| \geq |D| = γ (G)$

$\begin{array}{l} n = |D| + |V - D| \\ \Rightarrow n \geq 2 |D| \\ \Rightarrow n \geq 2 γ (G) \\ \Rightarrow γ (G) \leq \frac{n}{2} \\ \Rightarrow (G) \leq ⌊\frac{n}{2}⌋ \end{array}$

نکته

1- اگر $G$ بدون راس منفرد باشد به‌عبارتی $δ (G) \geq 1$ آن‌گاه داریم:

$\{\begin{array}{l} γ (G) \leq \frac{n}{2} \\ γ (\bar{G}) \leq \frac{n}{2} \end{array}〉 γ (G) + γ (\bar{G}) \leq n$

2- اگر $G$ دارای یک راس منفرد باشد آن‌گاه $γ (\bar{G}) = 1$ و $δ (G) \leq n$ در نتیجه:

$γ (G) + γ (\bar{G}) \leq n + 1$

اگر $G$ دارای یک راس منفرد باشد آن‌گاه $γ (G) = 1$ و $δ (G) \leq n$ در نتیجه:

$γ (G) + γ (\bar{G}) \leq n + 1$

قضیه

کران بالا و کران پایین برای عدد احاطه‌گری

اگر $G$ گرافی از مرتبه $n$ باشد که $n \geq 2$ آن‌گاه:

$⌈\frac{n}{Δ + 1}⌉ \leq γ (G) \leq n - Δ$

اثبات

اگر $\deg (v)$ درجه هر راس $v$ از گراف $G$ باشد، واضح است که راس $v$ به تعداد $1 + \deg (v)$ از رئوس $G$ را احاطه می‌کند.

اگر $v$ چنان انتخاب شده باشد که $\deg (v) = △$ آن‌گاه راس $v$ می‌تواند $1 + △$ راس $G$ را احاطه می‌کند، به‌جز $n - (1 + △)$ راس $G$ که باقی می‌ماند.

چون هیچ‌کدام از $n - (1 + △)$ راس $G$ به‌وسیله $v$ احاطه نمی‌شوند، پس حداکثر به‌وسیله خودشان احاطه می‌شوند، در نتیجه $G$ حداکثر به‌وسیله:

$(n - (1 + Δ)) + 1 = n - Δ$

راس احاطه می‌شود، یعنی داریم:

$γ (G) \leq n - Δ; (1)$

برای اثبات قسمت دیگر نامساوی، فرض کنیم $γ (G) = k$ باشد، یعنی مجموعه زیر احاطه‌گر مینیمم $G$ باشد:

$D = \{v_{1}, v_{2}, v_{3}, \dots, v_{k}\}$

چون راس $v_{i}$ به تعداد $1 + \deg (v_{i})$ راس $G$ را احاطه می‌کند که $1 \leq i \leq k$ و راس‌های $D$ همه $n$ راس $G$ را احاطه می‌کنند، پس داریم:

$\sum_{i = 1}^{k} (1 + \deg (v_{i})) \geq n$

به‌ازای هر $i$ که $1 \leq i \leq k$ باشد، $1 + \deg (v_{i}) \leq 1 + Δ$ در نتیجه:

$\begin{array}{l} n \leq \sum_{i = 1}^{k} (1 + \deg (v_{i})) \leq k (1 + Δ) \end{array}$

$\begin{array}{l} \Rightarrow n \leq k (1 + Δ) \\ \Rightarrow \frac{n}{1 + Δ} \leq k; γ (G) = k \\ \Rightarrow ⌈\frac{n}{1 + Δ}⌉ \leq γ (G); (2) \end{array}$

$\{\begin{cases} (1) : γ (G) \leq n - Δ \\ (2) : ⌈\frac{n}{1 + Δ}⌉ \leq γ (G) \end{cases}$

$⌈\frac{n}{1 + Δ}⌉ \leq γ (G) \leq n - Δ$

نکته

1- اگر $G$ گرافی $k$ منتظم باشد، آن‌گاه $△ = k$ بنابراین داریم:

$⌈\frac{n}{1 + Δ}⌉ \leq γ (G) \leq n - Δ \Rightarrow ⌈\frac{n}{1 + k}⌉ \leq γ (G) \leq n - k$

2- با توجه به قضیه $(1)$ این بخش داریم:

$⌈\frac{n}{1 + k}⌉ \leq γ (G) \leq ⌊\frac{n}{2}⌋$

تمرین

گراف زیر را در نظر بگیرید:

عدد احاطه‌گری - پیمان گردلو

عدد احاطه‌گری گراف فوق را مشخص و ادعای خود را ثابت کنید.

مجموعه دوعضوی $\{a, c\}$ یک مجموعه احاطه گر است.

عدد احاطه‌گری این گراف کوچک‌تر یا مساوی $2$ است، یعنی:

$γ (G) \leq 2$

اگر $γ (G) = 1$ یعنی یک راس در گراف فوق وجود دارد که به تنهایی تمام رئوس دیگر را احاطه می‌کند. (به تمام رئوس دیگر وصل است)

یعنی راسی با درجه چهار در گراف وجود دارد، که با توجه به گراف فوق چنین راسی وجود ندارد.

$1 < γ (G) \leq 2 \Rightarrow γ (G) = 2$

روش دیگر تحلیل این مساله به‌صورت زیر است:

$⌈\frac{n}{Δ + 1}⌉ \leq γ (G)$

$\begin{matrix} \Rightarrow ⌈\frac{5}{3 + 1}⌉ \leq γ (G) \end{matrix}$

$\begin{matrix} \Rightarrow ⌈1.25⌉ \leq γ (G) \\ \Rightarrow 2 \leq γ (G) \end{matrix}$

با توجه به مجموعه احاطه‌گری دو عضوی $\{a, c\}$ داریم:

$γ (G) = 2$

تمرین

عدد احاطه‌گری را برای هریک از گراف‌های زیر مشخص کنید:

$γ (G) \geq ⌈\frac{n}{Δ + 1}⌉ = ⌈\frac{10}{3 + 1}⌉ = 3 \Rightarrow γ (G) \geq 3$

مجموعه سه‌عضوی $\{a, c, h\}$ مجموعه احاطه‌گرِ مینیمم گراف فوق است، بنابراین:

$γ (G) = 3$

$γ (H) \geq ⌈\frac{n}{Δ + 1}⌉ = ⌈\frac{8}{2 + 1}⌉ = 3 \Rightarrow γ (H) \geq 3$

مجموعه سه‌عضوی $\{a, b, c\}$ مجموعه احاطه‌گرِ مینیمم گراف فوق است، بنابراین:

$γ (G) = 3$

$γ (G) \geq ⌈\frac{n}{Δ + 1}⌉ = ⌈\frac{8}{3 + 1}⌉ = 2 \Rightarrow γ (G) \geq 2$

مجموعه دو ‌عضوی $\{b, h\}$ مجموعه احاطه‌گرِ مینیمم گراف فوق است، بنابراین:

$γ (G) = 2$

$γ (G) \geq ⌈\frac{n}{Δ + 1}⌉ = ⌈\frac{10}{4 + 1}⌉ = 2 \Rightarrow γ (G) \geq 2$

مجموعه دو ‌عضوی $\{j, e\}$ مجموعه احاطه‌گرِ مینیمم گراف فوق است، بنابراین:

$γ (G) = 2$

$γ (G) \geq ⌈\frac{n}{Δ + 1}⌉ = ⌈\frac{12}{5 + 1}⌉ = 2 \Rightarrow γ (G) \geq 2$

مجموعه سه ‌عضوی $\{i, f, j\}$ مجموعه احاطه‌گرِ مینیمم گراف فوق است، بنابراین:

$γ (G) = 3$

$γ (G) \geq ⌈\frac{n}{Δ + 1}⌉ = ⌈\frac{19}{5 + 1}⌉ = 4 \Rightarrow γ (G) \geq 4$

مجموعه پنج ‌عضوی $\{g, i, k, l, e\}$ مجموعه احاطه‌گرِ مینیمم گراف فوق است، بنابراین:

$γ (G) = 5$

$γ (G) \geq ⌈\frac{n}{Δ + 1}⌉ = ⌈\frac{20}{5 + 1}⌉ = 4 \Rightarrow γ (G) \geq 4$

از هر پنج ضلعی حداقل دو راس باید انتخاب کنیم:

$γ (G) = 4 \times 2 = 8$

تمرین

گراف زیر را در نظر بگیرید:

عدد احاطه‌گری - پیمان گردلو

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

ابتدا حداقل تعداد رئوس برای احاطه کردن رئوس دیگرِ گراف فوق را پیدا می‌کنیم:

$⌈\frac{n}{Δ + 1}⌉ = ⌈\frac{12}{3 + 1}⌉ = 3$

حال با تحلیل زیر $γ (G)$ را می‌یابیم:

برای احاطه کردن راس $a$ لازم است یکی از دو راس $a, b$ در مجموعه احاطه‌گر باشد.

به‌همین ترتیب یکی از رئوس $e, f$ و نیز یکی از رئوس $i, j$ باید در هر مجموعه احاطه‌گر باشند.

اما این سه راس انتخاب شده در هر حالت نمی‌توانند رئوس $d, h, l$ را احاطه کنند، لذا حداقل یک راس دیگر یعنی حداقل $4$ راس برای احاطه رئوسِ این گراف لازم است.

$γ (G) \geq 4$

از طرفی $\{b, f, j, h\}$ یک مجموعه احاطه‌گر است و $γ (G) \leq 4$ بنابراین:

$γ (G) = 4$

تمرین

گراف زیر را در نظر بگیرید:

عدد احاطه‌گری - پیمان گردلو

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

ابتدا حداقل تعداد رئوس برای احاطه کردن رئوس دیگرِ گراف فوق را پیدا می‌کنیم:

$⌈\frac{n}{Δ + 1}⌉ = ⌈\frac{8}{3 + 1}⌉ = 2$

برای احاطه کردن راس $h$ حداقل یکی از رئوس $h$ یا $e$ باید در مجموعه احاطه‌گر باشند و با بودن هر کدام از آنها در مجموعه احاطه‌گر، رئوس $a, b, c, g$ کماکان احاطه نشده باقی می‌مانند.

برای احاطه کردن رئوس $a, b, c, g$ حداقل دو راس دیگر نیاز است، زیرا هیچ راسی به تنهایی نمی‌تواند هر چهارتای آنها را احاطه کند.

بنابراین حداقل $3$ راس باید در هرمجموعه احاطه‌گر از گراف $G$ باشد، یعنی:

$γ (G) \geq 3$

از طرفی چون $\{a, c, e\}$ یک مجموعه احاطه‌گر مینیمم است لذا:

$γ (G) = 3$

قضیه

به‌ازای هر عدد صحیح و مثبت $n$ و عدد صحیح $k$ که $1 \leq k \leq n$ گرافی وجود دارد که:

$γ (G) = k$

اثبات

فرض کنیم که $G$ گرافی از مرتبه $n$ باشد، مجموعه راس‌های آن به‌صورت زیر است:

$V = \{a_{1}, a_{2}, a_{3}, ....., a_{n - 1}, a_{n}\}$

اگر $G$ گرافی تهی $k_{n}$ باشد، واضح است که $γ (G) = n$ .

اگر فقط یال $a_{1} a_{2}$ را رسم کنیم، $n - 2$ راس باقی مانده که همه منفرد هستند، دارای عدد احاطه‌گری $γ (G) = n-2$ است.

اکنون $v_{1} = \{a_{1}, a_{2}\}$ دارای عدد احاطه‌گری $(1)$ است، پس در این گراف کلا عدد احاطه‌گری عبارت است از $γ (G) = n-1$ .

اگر یال $a_{3} a_{4}$ را رسم کنیم، $γ (G) = n - 2$ خواهد بود و تا $\frac{n}{2}$ می‌توان ادامه داد. بنابراین تا حالتی که $k \geq \frac{n}{2}$ این عدد مشخص می‌شود.

اگر $1 \leq k \leq \frac{n}{2}$ همواره می‌توان گرافی همبند پیدا کرد که:

$γ (G) = k$

قضیه

برای هر دو عدد صحیح $n$ و $k$ که $1 \leq k \leq \frac{n}{2}$ همواره یک گراف همبند از مرتبه $n$ وجود دارد که:

$γ (G) = k$

اثبات

قبل از اثبات قضیه، به مثال عددی زیر توجه کنید:

فرض کنید $n = 9$ و $1 \leq k \leq \frac{n}{2} < 5$ پس $k$ می‌تواند اعداد زیر را اختیار کند:

$k = 1, 2, 3, 4$

فرض کنیم $k = 4$ باشد، پس گراف کامل $k_{9 - 4} = k_{5}$ را در نظر می‌گیریم که در آن $γ (k_{5}) = 1$ .

عدد احاطه‌گری - پیمان گردلو

اکنون چهار راس $u_{4}, u_{3}, u_{2}, u_{1}$ را به گراف $k_{5}$ اضافه می‌کنیم و یال‌های $v_{4} u_{4}, v_{3} u_{3}, v_{2} u_{2}, v_{1} u_{1}$ را رسم می‌کنیم.

گراف همبند $G$ از مرتبه $9$ پدید می‌آید که:

$γ (G) = 4$

عدد احاطه‌گری - پیمان گردلو

حال به اثبات قضیه می‌پردازیم:

گراف کامل $K_{n - k}$ شامل $n - k$ راس $\{v_{1}, v_{2,} ...., v_{n - k}\}$ را رسم می‌کنیم، واضح است که:

$γ (K_{n - k}) = 1$

اکنون $k$ راس جدید $u_{k}, ...., u_{2}, u_{1}$ را به آن اضافه می‌کنیم، پس گراف همبند $G$ از مرتبه $n$ پدید می‌آید.

$k$ یال جدید $v_{i} u_{i}$ که $1 \leq i \leq k \leq \frac{n}{2}$ را رسم می‌کنیم.

پس از همه راس‌های $u_{k}, ...., u_{2}, u_{1}$ که $k$ راس $K_{n - k}$ یالی رسم شده، ممکن است به‌راسی از آن یالی متصل نشده باشد.

چون $k \leq n - k$ پس کافی است مجموعه احاطه‌گر $G$ را همان $k$ راس از $n - k$ راس $K_{n - k}$ انتخاب کنیم، در این‌صورت:

$γ (G) = k$

تمرین

گرافی از مرتبه $n \geq 4$ مشخص کنید که در آن $γ (G) = 2$ باشد.

کافی است دو گراف ستاره‌ای رسم و راس‌های ستاره‌ها را به‌هم وصل کنید اگر هم‌راس‌های دو ستاره را به‌هم وصل نکنیم، یک گراف ناهمبند پدید می‌آید.

عدد احاطه‌گری - پیمان گردلو

تست‌های این مبحث

تست شماره 1

در گرافی ساده از مرتبه $13$ بیشترین درجه راس ها برابر $5$ است.

عدد احاطه گری این گراف کدام عدد می‌تواند باشد؟

$10$
$2$
$9$
$5$

مشاهده پاسخ تست

برای ارسال نظر وارد سایت شوید

گراف

مدل‌ سازی (عدد احاطه‌ گری)

تعریف عدد احاطه‌گری

تست‌های این مبحث

nenomatica

مجموعه قوانین

دسترسی سریع

آیا می‌خواهید فیلم معرفی را مشاهده نمایید؟