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

گراف

درجه گراف ساده

آخرین ویرایش: 20 آبان 1403

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

امتیاز:

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

تعریف درجه گراف ساده

مجموعه راس‌های گراف ساده $G$ به‌صورت زیر را در نظر بگیرید:

$V (G) = \{v_{1}, v_{2}, .., v_{k}, ... v_{p}\}$

درجه هر راس از گراف ساده $G$ برابر تعداد یال‌هایی از $G$ است که از راس $v_{k}$ می‌گذرند و این عدد را با $\deg v_{k}$ نمایش می‌دهند.

اگر $\deg v_{k}$ یک عدد فرد باشد، $v_{k}$ را یک راس فرد گویند.
اگر $\deg v_{k}$ یک عدد زوج باشد، $v_{k}$ را یک راس زوج گویند.
بزرگ‌ترین عدد در بین درجه‌های راس‌های گراف $G$ را ماکزیمم درجه $G$ می‌نامند و با $(△)$ نشان می‌دهند.
کوچک‌ترین عدد در بین درجه‌های راس‌های گراف $G$ را مینیموم درجه $G$ می‌نامند و با $(δ)$ نشان می‌دهند.

تمرین

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

درجه راس‌های این گراف را بنویسید.

$\begin{array}{l} \deg (a) = 3 \\ \deg (b) = 3 \\ \deg (c) = 4 \\ \begin{matrix} \deg (d) = 2 \end{matrix} \\ \deg (e) = 2 \\ \deg (f) = 0 \end{array}$

دو راس از درجه فرد است و چهار راس از درجه زوج است، راس $f$ را که درجه‌اش صفر است، راس تنها گویند.

تمرین

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

درجه گراف ساده - پیمان گردلو

$m a x$ و $m i n$ درجه این گراف را بنویسید.

$\{\begin{cases} Δ = 5 \\ δ = 2 \end{cases}$

تمرین

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

گراف شكل فوق چند راس فرد وجود دارد؟

راس فرد به راسی گفته می‌شود كه درجه اش فرد باشد.

پس گراف فوق دو راس فرد دارد.

تمرین

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

ماكزيمم درجه و مينيمم درجه در بين درجه های راس های گراف داده شده در شكل فوق را بنویسید.

$δ = 1, Δ = 5$

تمرین

گراف G با مجموعه رئوس زیر را در نظر بگیرید:

$V = \{a, b, c, d, e\}$

چند گراف G وجود دارد كه داشته باشيم:

$\begin{array}{l} \deg (a) = \deg (b) = 2 \\ \deg (c) = \deg (d) = \deg (e) = 4 \end{array}$

چون درجه هر يک از راس های $e, d, c$ برابر $4$ است، پس هر كدام از اين راس ها به چهار راس ديگر متصل است.

بنابراين راس $a$ به سه راس $e, d, c$ متصل است.

در نتيجه داریم:

$\deg (a) \geq 3$

كه خلاف فرض است، پس چنين گرافی وجود ندارد.

تمرین

گراف G با مجموعه رئوس زیر را در نظر بگیرید:

$V = \{a, b, c, d\}$

آيا گرافی وجود دارد كه داشته باشیم:

$\begin{array}{l} \deg a = \deg b = 1 \\ \deg c = \deg d = 3 \end{array}$

چون درجه $c$ عدد $3$ است پس سه یال از $c$ به $a, b, d$ وجود دارد.

به‌همين دليل سه يال از $d$ به $a, b, c$ وجود دارد.

بنابراين گراف G بايد به‌صورت زير باشد:

بنابراين داریم:

$\begin{array}{l} \deg a \geq 2 \\ \deg b \geq 2 \end{array}$

كه خلاف فرض است، بنابراين گرافی با مشخصات فوق وجود ندارد.

تمرین

فرض كنيد مجموعه های زیر به‌ترتيب مجموعه راس و يال گراف G باشند:

$\begin{array}{l} V = \{v_{1}, ..., v_{4}\} \end{array}$

$E = \{(v_{1}, v_{2}), (v_{1}, v_{3}), (v_{4}, v_{1}), (v_{3}, v_{4}), (v_{2}, v_{3}), (v_{4}, v_{3})\}$

در اين‌صورت درجه راس $v_{3}$ را به‌دست آورید.

چون راس $v_{3}$ در سه زوج مرتب، مولفه دوم قرار گرفته است، لذا سه يال به آن وارد شده است:

$\deg (v_{3}) = 3$

تمرین

در گراف از مرتبه $8$ و اندازه $25$ حداقل چند راس از درجه $△$ وجود دارد؟

دراين گراف بايد $△ = 7$ باشد.

اگر $△ < 7$ باشد، آن‌گاه تعداد يال ها كمتر از $25$ می‌شود.

اگر همه راس ها از درجه $7$ باشد، مجموع درجات برابر است با:

$7 \times 8 = 56$

در صورتی كه در اين گراف مجموع درجات برابر است با:

$2 \times 25 = 50$

حال بايد اين اختلاف $6$ واحد را بين حداكثر تعداد راس ها توزيع كرد تا حداقل تعداد راس ها با درجه $△$ به‌دست آيد.

يعنی دنباله گرافی چنين گرافی به‌صورت زیر است.

$(v, v, y, y, y, y, y, y)$

كه دارای $2$ راس از درجه $△ = 7$ است.

دریافت مثال

دریافت فایل PDF

قضایای درجه گراف ساده

قضیه

مجموع درجات تمام راس‌ها در گراف ساده $G$ دوبرابر اندازه $G$ یعنی $q$ تعداد یال‌های $G$ می‌باشد:

$\sum_{i = 1}^{p} \deg (V_{i}) = 2 q$

اثبات

اثبات این قضیه از این واقعیت نتیجه می‌شود که هنگام شمارش درجه راس‌های یک گراف $G$ هر یال دو بار شمارش می‌شود.

قضیه فوق در یک گراف غیرساده هم صادق است (گراف‌های چندگانه).با توجه به فرمول فوق، درجه کل یک گراف، زوج است.

تمرین

گراف ساده $G$ از مرتبه شش، سه راس از درجه چهار و سه راس از درجه دو دارد، اندازه آن را به‌دست آورید.

$\begin{array}{l} \sum_{i = 1}^{6} \deg (V_{i}) = 2 q \end{array}$

$\begin{array}{l} \Rightarrow (4 + 4 + 4) + (2 + 2 + 2) = 2 q \end{array}$

$\begin{array}{l} \begin{array}{l} \Rightarrow 18 = 2 q \\ \Rightarrow q = 9 \end{array} \end{array}$

گراف ساده $G$ دارای $24$ یال می‌باشد، اين گراف $3$ راس از درجه دو $3$ راس از درجه شش و بقيه راس ها از درجه سه هستند، اين گراف چند راس دارد.

$\begin{array}{l} \sum \deg (V_{i}) = 2 q \\ \Rightarrow (3 \times 2) + (3 \times 6) + 3 k = 2 (24) \\ \Rightarrow k = 8 \end{array}$

تعداد راس ها برابر است با:

$3 + 3 + 8 = 14$

اگر اندازه گراف ساده $G$ (تعداد یال های گراف) هشت باشد، مجموعه درجات تمام راس های $G$ را به‌دست آورید.

$\begin{array}{l} \sum_{i = 1}^{p} \deg (V_{i}) = 2 q; q = 8 \\ \Rightarrow \sum_{i = 1}^{p} \deg (V_{i}) = 2 \times 8 \\ \Rightarrow \sum_{i = 1}^{p} \deg (V_{i}) = 16 \end{array}$

تمرین

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

در گراف فوق تعداد راس ها، يال ها و درجه هر راس را مشخص كنيد و نشان دهيد كه مجموع درجات رئوس دو برابر تعداد يال ها است.

$\begin{array}{l} V (G) = \{a, b, c, d, e\} \Rightarrow p = |V (G)| = 5 \end{array}$

$E (G) = \{\{a, b\}, \{a, c\}, \{a, d\}, \{b, c\}, \{b, e\}, \{c, d\}, \{c, e\}\} \Rightarrow q = |E (G)| = 7$

$5$ راس و $7$ يال به در گراف فوق موجود است.

$\sum \deg V_{i} = 3 + 3 + 4 + 2 + 2 = 14 = 2 (7)$

تمرین

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

در گراف فوق، تعداد يال ها را با مجموع درجه های راس ها مقايسه نمائيد.

ابتدا درجه همه راس ها را می‌يابيم:

$\begin{array}{l} \deg (a) = \deg (c) = 4 \\ \deg (b) = \deg (d) = 3 \\ \deg (e) = 5 \\ \deg (f) = 1 \end{array}$

بنابراين مجموع درجه های راس های اين گراف به‌صورت زیر است:

$\deg (a) + \deg (c) + \deg (b) + \deg (d) + \deg (e) + \deg (f) = 4 + 4 + 3 + 3 + 5 + 1 = 20$

كه اين مقدار دو برابر تعداد يال ها است.

$q = 10$

تمرین

اگر داشته باشیم:

$V (G) = \{A, B, C, D\}$

$m$ ،درجه راس های G را در حالات زیر به‌دست آورید.

$E (G) = \{\{A, B\}, \{A, C\}, \{A, D\}, \{B, D\}\}$

مجموع راس های گراف G دو برابر تعداد يال های آن است:

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

اين گراف $4$ يال دارد در نتيجه:

$m = 2 (4) = 8$

$E (G) = \{\{A, B\}, \{A, C\}, \{A, D\}, \{B, A\}, \{B, B\} \{C, B\}, \{C, D\}\}$

اين گراف $7$ يال دارد در نتيجه:

$m = 2 (7) = 14$

تمرین

در گرافی با $9$ يال، درجه تمامی راس ها برابر $3$ می‌باشد.

تعداد راس ها چند است؟

$\begin{array}{l} \sum_{} \deg (V_{i}) = 2 q \\ \Rightarrow 3 n = 2 \times 9 \\ \Rightarrow n = 6 \end{array}$

تمرین

فرض كنيد G يک گراف ساده است.

در این گراف $V$ ، $12$ عضو دارد و درجه هر راس آن برابر با $4$ است.

در اين‌صورت G چند يال دارد؟

مجموع درجه های راس های يک گراف دو برابر تعداد يال هاست.

پس اگر q تعداد يال های گراف مورد نظر باشد، آن‌گاه:

$\begin{array}{l} \sum_{}^{} \deg (V_{i}) = 2 q \\ \Rightarrow 12 \times 4 = 2 q \\ \Rightarrow q = 24 \end{array}$

تمرین

درجه كليه رئوس يک گراف از مرتبه $6$ برابر $3$ است.

اين گراف چند يال دارد؟

$\begin{array}{l} \sum_{i = 1}^{p} \deg V_{i} = 2 q \\ \Rightarrow \sum_{i = 1}^{6} 3 = 2 q \end{array}$

$\begin{array}{l} \Rightarrow 3 \times 6 = 2 q \\ \Rightarrow q = 9 \end{array}$

تمرین

گرافی دارای $4$ راس از درجه $5$ بوده و مرتبه و اندازه‌اش به‌ترتيب $6, 14$ است.

مجموع درجات راس های باقی مانده را بیابید.

$\begin{array}{l} \sum \deg (v_{i}) = 2 q \end{array}$

$\begin{array}{l} \Rightarrow (4 \times 5) + x = 2 \times 14; \{\begin{cases} p = 6 \\ q = 14 \end{cases} \end{array}$

$\Rightarrow x = 8$

تمرین

گراف G دارای $10$ يال و دو راس از درجه $4$ و بقيه راس ها از درجه $3$ می‌باشند.

تعداد راس های آن را به‌دست آورید.

$\begin{array}{l} \sum \deg (v_{i}) = 2 q \\ \Rightarrow 2 \times 4 + k \times 3 = 2 \times 10 \end{array}$

$\begin{array}{l} \Rightarrow k \times 3 = 12 \\ \Rightarrow k = 4 \end{array}$

تعداد راس ها:

$2 + k = 2 + 4 = 6$

تمرین

گراف ساده $G$ دارای $10$ يال و $2$ راس از درجه $4$ و بقيه راس ها از درجه $3$ می‌باشد.

مرتبه اين گراف را به‌دست آورید.

فرض می‌كنيم تعداد راس های با درجه $3$ برابر $n$ است:

$\begin{array}{l} \sum \deg (V_{i}) = 2 q \\ \Rightarrow (2 \times 4) + (3 \times n) = 20 \end{array}$

$\begin{array}{l} \Rightarrow 8 + 3 n = 20 \\ \Rightarrow n = 4 \end{array}$

پس تعداد راس های با درجه $3$ برابر $4$ است و $2$ راس از درجه $4$ نيز وجود دارد، بنابراين تعداد كل راس ها برابر $6$ می‌باشد.

تمرین

يک گراف از مرتبه $12$ و اندازه $16$ فقط دارای راس های درجه $2$ و درجه $3$ است.

اين گراف چند راس از درجه $2$ دارد؟

$\begin{array}{l} \{\begin{cases} p = x + y = 12 \\ \sum \deg V_{i} = 2 q \Rightarrow 2 x + 3 y = 2 \times 16 \end{cases} \end{array}$

$\begin{array}{l} \Rightarrow \{\begin{cases} x + y = 12 \\ 2 x + 3 y = 32 \end{cases} \end{array}$

$\Rightarrow \{\begin{cases} x = 4 \\ y = 8 \end{cases}$

اين گراف $4$ راس درجه $2$ دارد.

تمرین

آيا ممكن است در يک گروه $9$ نفری، هر شخص به تنهايی با $5$ نفر ديگر دوست باشد؟

خير. اگر هر نفر نماينده يک راس باشد و با $5$ نفر دوست باشد يعنی درجه اين نقطه $5$ است.

$\deg (V_{i}) = \underset{9}{\underset{⏟}{5 + 5 + 5 + ... + 5}} = 45$

در تساوی فوق، مجموع درجات $45$ است که عددی فرد است.

می‌دانيم مجموع كل درجه يک گراف همواره زوج است.

تمرین

در گرافی با $31$ راس كه درجه هر راس حداكثر $3$ می‌باشد.

بيشترين تعداد يال را به‌دست آورید؟

هر $31$ راس نمی‌تواند از درجه فرد باشد چون تعداد رئوس ازدرجه فردشظ بايد زوج باشد.

پس حداكثر تعداد يال وقتی ايجاد می‌شود كه $30$ راس از درجه $3$ و $1$ راس از درجه $2$ داشته باشد:

$\begin{array}{l} \sum \deg (V_{i}) = 2 q \\ \Rightarrow 30 (3) + 1 (2) = 2 q \end{array}$

$\begin{array}{l} \Rightarrow 92 = 2 q \\ \Rightarrow q = 46 \end{array}$

تمرین

گرافی $20$ يال دارد كه درجه هر راس آن حداقل $4$ است.

بيشترين تعداد راس را بیابید.

$\begin{array}{l} \sum \deg (V_{i}) = 2 q \\ \Rightarrow 4 x = 40 \\ \Rightarrow x = 10 \end{array}$

چون حداقل درجه هر راس $4$ است، پس حداكثر تعداد راس ها برابر $10$ است.

تمرین

فرض كنيد $G$ گرافی است كه درجه هر راس آن $6$ يا $7$ است.

ثابت كنيد تعداد راس های درجه $6$ اين گراف برابر است با:

$7 p - 2 q$

فرض كنيم $x$ تعداد راس های با درجه $6$ در این گراف است.

$y$ تعداد راس های با درجه $7$ در اين گراف است.

پس اين گراف $x + y$ راس دارد، بنابراين:

$p = x + y \Rightarrow y = p - x$

$\begin{array}{l} \sum_{i = 1}^{p} \deg (V_{i}) = 2 q \end{array}$

$\begin{array}{l} \Rightarrow (6 + 6 + ... + 6) + (7 + 7 + ... + 7) = 2 q \end{array}$

$\begin{array}{l} \Rightarrow 6 x + 7 y = 2 q; y = p - x \\ \Rightarrow 6 x + 7 (p - x) = 2 q \end{array}$

$\begin{array}{l} \Rightarrow 6 x + 7 p - 7 x = 2 q \\ \Rightarrow - x = 2 q - 7 p \\ \Rightarrow x = 7 p - 2 q \end{array}$

تمرین

گرافی با $23$ راس و $△ = 5$ را در نظر بگیرید.

اين گراف حداكثر چند يال می‌تواند داشته باشد؟

حداكثر تعداد يال ها در اين گراف وقتی است كه همه راس ها حداكثر درجه يعنی درجه $5$ را داشته باشند.

اما چون اين گراف $23$ راس دارد، بنابراين هر $23$ راس نمی‌تواند از درجه $5$ باشند.

در نتيجه بايد $22$ راس از درجه $5$ و يک راس ديگر از درجه $4$ باشد.

در اين‌صورت حداكثر تعداد يال ها برابر است با:

$\begin{array}{l} \sum_{i = 1}^{p} \deg (V_{i}) = 2 q \\ \Rightarrow \Rightarrow 22 (5) + 1 (4) = 2 q \\ \Rightarrow q = 57 \end{array}$

تمرین

$17$ نفر به سفر می‌روند و قبل از سفر قرار می‌گذارند هركس به پنج نفر ديگر نامه بفرستد.

آيا امكان دارد هر كس به آن $5$ نفری نامه بفرستد كه از آنها نامه دريافت می‌كند؟

خیر.

اگر گرافی رسم كنيم كه راس های آن 17 نفر مذكور و يال های آن معرف فرستادن و دريافت نامه باشد، در اين‌صورت (اگر هركس به همان $5$ نفری نامه بفرستد كه از آنها دريافت كرده) مجموع درجه های راس ها برابر است با:

$17 \times 5 = 85$

زيرا هر راس از درجه $5$ می‌باشد.

از طرفی می‌دانيم مجموع درجه های راس ها در يک گراف، عددی زوج است.

پس اين مجموع نمی‌تواند عدد $85$ باشد، لذا چنين گرافی وجود ندارد.

تمرین

كدام‌يک از وضعيت‌های زير می‌تواند وجود داشته باشد؟

در يک گروه $17$ نفره، هر شخص فقط با يک نفر دست می‌دهد.

$17 \times 1 = 17$

مجموع درجه های راس های آن عددی فرد است.

برای این وضعیت گرافی قابل رسم نیست.

در يک گروه $15$ نفره، هر شخص فقط با سه نفر دست می‌دهد.

$15 \times 3 = 45$

مجموع درجه های راس های آن عددی فرد است.

برای این وضعیت گرافی قابل رسم نیست.

در يک گروه $27$ نفره، هر شخص فقط با چهار نفر دست می‌دهد.

$27 \times 4 = 108$

تنها برای اين وضعيت می‌توان گرافی رسم كرد كه مجموع درجه های راس های آن عددی زوج است.

دریافت مثال

دریافت فایل PDF

قضیه

نامساوی زیر همواره برقرار است:

$δ \leq \frac{2 q}{p} \leq Δ$

اثبات

مجموعه راس‌های گراف ساده $G$ به‌صورت زیر را در نظر بگیرید:

$V (G) = \{v_{1}, v_{2}, .., v_{k}, ... v_{p}\}$

$(1 \leq i \leq p)$

$\begin{array}{l} δ \leq \deg V_{i} \leq Δ \\ \Rightarrow \sum_{i = 1}^{p} δ \leq \sum_{i = 1}^{p} \deg V_{i} \leq \sum_{i = 1}^{p} Δ \end{array}$

$\begin{array}{l} \Rightarrow (δ + δ + ... + δ) \leq \sum_{i = 1}^{p} \deg V_{i} \leq (Δ + Δ + ... + Δ) \end{array}$

$\begin{array}{l} \Rightarrow p δ \leq 2 q \leq p Δ \\ \Rightarrow \frac{p δ}{p} \leq \frac{2 q}{p} \leq \frac{p Δ}{p} \\ \Rightarrow δ \leq \frac{2 q}{p} \leq Δ \end{array}$

تمرین

در گرافی با $35$ راس كه ماكزيمم درجه آن سه است، بيش‌ترين تعداد يال را تعيين كنيد.

$\begin{array}{l} δ \leq \frac{2 q}{p} \leq Δ \\ \Rightarrow 2 q \leq p Δ \\ \Rightarrow 2 q \leq 35 \times 3 \end{array}$

$\begin{array}{l} \Rightarrow q \leq \frac{35 \times 3}{2} \\ \Rightarrow q \leq 52.5 \\ \Rightarrow q = 52 \end{array}$

تمرین

گرافی از مرتبه $11$ و داریم:

$\{\begin{cases} Δ = 6 \\ δ = 4 \end{cases}$

اندازه اين گراف در چه بازه‌ای قرار دارد؟

$\begin{array}{l} δ \leq \frac{2 q}{p} \leq Δ \\ \Rightarrow 4 \leq \frac{2 q}{11} \leq 6 \\ \Rightarrow 22 < q < 33 \end{array}$

تمرین

در گراف $G$ حداقل درجه راس ها و حداكثر درجه راس ها دو عدد متوالی هستند.

اگر اين گراف دارای $7$ راس و $18$ يال باشد:

حداقل درجه راس ها را به‌دست آورید؟

$\begin{array}{l} Δ = δ + 1 \\ δ \leq \frac{2 q}{p} \leq Δ \end{array}$

$\begin{array}{l} \Rightarrow δ \leq \frac{2 q}{p} \leq δ + 1; \{\begin{cases} p = 7 \\ q = 18 \end{cases} \end{array}$

$\begin{array}{l} \Rightarrow δ \leq \frac{2 \times 18}{7} \leq δ + 1 \\ \Rightarrow δ \leq \frac{36}{7} \leq δ + 1 \end{array}$

$\begin{array}{l} \Rightarrow 5 \leq \frac{36}{7} \leq 6 \\ \Rightarrow δ = 5 \end{array}$

تمرین

در يک گراف ساده، بزرگ ترين و كوچک ترين درجه در بين درجه های راس ها به ترتيب سه و یک می‌باشد.

اگر اين گراف $2 n$ راس داشته باشد و تعداد يال هايش $11$ باشد:

حدود $n$ را به‌دست آورید.

$\begin{array}{l} δ \leq \frac{2 q}{p} \leq Δ \\ \Rightarrow 1 \leq \frac{2 \times 11}{2 n} \leq 3 \\ \Rightarrow \frac{1}{3} \leq \frac{2 n}{22} \leq 1 \end{array}$

$\begin{array}{l} \Rightarrow \frac{1}{3} \leq \frac{n}{11} \leq 1 \\ \Rightarrow \frac{11}{3} \leq n \leq 11 \end{array}$

چون $n$ مقادير طبيعی را اختيار می‌كند، پس:

$3 \leq n \leq 11$

تمرین

در يک گراف ساده، بزرگ ترين و كوچک ترين درجه در بين درجه های راس ها به‌ترتيب $2, 5$ می‌باشد.

اگر اندازه اين گراف عدد $11$ باشد:

بيش ترين و كم ترين عدد در مورد مرتبه اين گراف را به‌دست آورید.

$\begin{array}{l} δ \leq \frac{2 q}{p} \leq Δ \\ \Rightarrow 2 \leq \frac{2 \times 15}{p} \leq 5 \end{array}$

$\begin{array}{l} \Rightarrow \frac{1}{5} \leq \frac{p}{30} \leq \frac{1}{2} \\ \Rightarrow 6 \leq p \leq 15 \end{array}$

تمرین

در يک گراف ساده داریم:

$δ = Δ = 2$

اگر مرتبه گراف $5$ باشد، آن‌گاه اندازه گراف را به‌دست آورید.

$\begin{array}{l} δ \leq \frac{2 q}{p} \leq Δ \\ \Rightarrow 2 \leq \frac{2 q}{5} \leq 2 \end{array}$

$\begin{array}{l} \Rightarrow \frac{2 q}{5} = 2 \\ \Rightarrow 2 q = 10 \\ \Rightarrow q = 5 \end{array}$

تمرین

فرض كنيد $G$ گراف ساده ای با $17$ يال باشد.

اگر در اين گراف داشته باشيم $δ = 3$ :

اين گراف حداكثر چند راس دارد؟

$\begin{array}{l} δ \leq \frac{2 q}{p} \leq Δ \\ \Rightarrow \frac{2 q}{p} \geq δ \end{array}$

$\begin{array}{l} \Rightarrow 2 q \geq p δ \\ \Rightarrow 2 (17) \geq p (3) \end{array}$

$\begin{array}{l} \Rightarrow p \leq \frac{34}{3} \\ \Rightarrow p \leq 11 \\ \Rightarrow \max (p) = 11 \end{array}$

دریافت مثال

دریافت فایل PDF

قضیه

در هر گراف ساده تعداد راس‌هایی که درجه آنها فرد است، عددی زوج است.

اثبات

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

باید ثابت کنیم که $n$ عددی زوج است.

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

فرض کنید $E$ مجموع درجه‌های همه راس‌های از درجه زوج و $O$ مجموع درجه‌های همه راس‌های از درجه فرد و $T$ درجه کل گراف $G$ باشد.

اگر $u_{1}, u_{2}, ..., u_{m}$ راس‌های از درجه زوج و $V_{1}, V_{2}, ..., V_{n}$ راس‌های از درجه فرد گراف $G$ باشد، آن‌گاه:

$\begin{array}{l} E = \deg (u_{1}) + \deg (u_{2}) + ... + \deg (u_{m}) \end{array}$

$\begin{array}{l} O = \deg (V_{1}) + \deg (V_{2}) + ... + \deg (V_{n}) \end{array}$

$T = \deg (u_{1}) + ... + \deg (u_{m}) + \deg (V_{1}) + ... + \deg (V_{n}) = E + O$

$T$ یعنی درجه کل گراف $G$ که یک عدد صحیح زوج است و هم‌چنین $E$ زوج است زیرا یا $E$ برابر صفر است که زوج است یا $E$ مجموع اعداد $\deg (u_{i})$ هاست که هر یک از اینها زوج هستند، اما:

$T = E + O \Rightarrow O = T - E$

تفاضل دو عدد صحیح، زوج است در نتیجه $O$ زوج است.

بنابر فرض به‌ازای همه مقادیر، درجه زیر فرد است:

$\deg (V_{i}); i = 1, 2, ..., n$

بنابراین $O$ یعنی یک عدد صحیح زوج ، برابر مجموع $n$ عدد صحیح فرد است:

$\deg (V_{n}), ..., \deg (V_{2}), \deg (V_{1})$

جمع $n$ عدد صحیح فرد، زوج می‌باشد، بنابراین $n$ زوج است.

به‌عنوان نمونه:

در یک مهمانی تعداد افرادی که با تعدادی فرد، از مهمان‌ها دست نداده‌اند، زوج است که جمله‌ای درست است.
تعداد تمام افرادی که به‌دفعات فرد ازدواج کرده‌اند زوج است که جمله‌ای درست است.
در یک دوره مسابقه فوتبال تعداد تیم‌هایی که با تعدادی فرد از تیم‌ها مسابقه داده‌اند فرد است که جمله‌ای غلط است.

نکته

1- اگر از راسی هیچ یالی عبور نکندا، درجه آن صفر است و آن را یک راس تنها (ایزوله) می‌گوییم.

2- اگر یک یال از گراف به‌صورت حلقه (طوقه) باشد، درجه آن راس دوبار شمارش می‌شود که در گراف‌های چندگانه مطرح است.

یادآوری می‌کنیم که طوقه، یالی است که ابتدا و انتهایش یک راس است.

به‌عنوان نمونه:

درجه راس $v_{1}$ در گراف فوق $5$ است.

3- برای محاسبه درجه یک راس باید تعداد یال‌هایی را شمرد که آن راس بر آنها واقع است.

4- با یک تعداد راس مشخص، درصورتی تعداد یال‌ها بیش‌تر می‌شود که درجه راس‌ها تا جای ممکنه بیش‌تر شود.

5- در یک نگاه ساده با $q$ یال مشخص، هر چه درجه راس‌ها کم‌تر باشد، تعداد راس‌ها بیش‌تر است.

6- حداقل دو راس از گراف $G$ دارای یک درجه هستند.

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

$0 \leq \deg V_{k} \leq p - 1$

برحسب آن‌که $\deg V_{k}$ زوج یا فرد باشد، راس $V_{k}$ زوج یا فرد است.

تمرین

بيش ترين تعداد يال برای گراف مرتبه $7$ كه درجه هر راس آن حداكثر $3$ باشد را به‌دست آورید.

با يک تعداد راس مشخص در صورتی تعداد يال ها بيش تر می‌شود كه درجه راس ها تا جايی كه ممكن است بيش تر باشد.

در اين تمرین بهتر است تعداد راس های درجه $3$ ماکزیمم باشد.

با توجه به اين‌كه هر $7$ راس نمی‌توانند درجه $3$ باشند (مجموع درجات نبايد فرد باشد) می‌توان $6$ راس را از درجه $3$ و يک راس را از درجه $2$ در نظر گرفت.

$\sum \deg (V_{i}) = (6 \times 3) + (1 \times 2) = 2 q \Rightarrow q = 10$

تمرین

در يک گراف با اندازه $10$ ، درجه هر راس حداقل $2$ می‌باشد.

ماکزیمم تعداد راس ها را به‌دست آورید.

در يک گراف ساده با $q$ يال مشخص، هر چه درجه راس ها كم تر باشد تعداد راس ها بيش تر خواهد بود.

$\begin{array}{l} \sum \deg (V_{i}) = 2 q \\ \Rightarrow \sum \deg (V_{i}) = 2 \times 10 \\ \Rightarrow \sum \deg (V_{i}) = 20 \end{array}$

اگر مجموع درجات راس های این گراف $20$ باشد و درجه هر راس حداقل $2$ باشد، می‌توانيم ماکزیمم $10$ راس درجه $2$ داشته باشيم.

دریافت مثال

دریافت فایل PDF

دنباله‌ های درجات راس‌ ها

اگر گراف ساده $G$ دارای $p$ راس باشد و درجات راس‌های آن به‌ترتیب به‌صورت زیر باشد:

$d_{p}, ... d_{2}, d_{1}$

به‌طوری‌که $\{\begin{cases} d_{i} \geq d_{i + 1} \\ i = 1, ..., p - 1 \end{cases}$ ، در این‌صورت:

$d_{1} \geq d_{2} \geq ... \geq d_{p}$

آن‌گاه دنباله زیر را دنباله درجات راسهای گراف ساده $G$ می‌نامیم:

$S : d_{1}, d_{2}, ..., d_{p}$

نکته

با توجه به تعریف گراف و مفاهیمی که از دنباله‌ها می‌دانیم، داریم:

1- وقتی که گراف ساده‌ای دارای $p$ راس باشد، بزرگ‌ترین درجه، حداکثر $(p - 1)$ است، به‌عبارت دیگر در دنباله، درجات راس‌ها همواره:

$d_{1} \leq p - 1$

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

3- در یک دنباله، مجموع درجات راس‌ها باید عددی زوج باشد، زیرا:

$\sum_{i = 1}^{p} \deg (V_{i}) = 2 q$

4- دنباله $S$ دنباله‌ای نزولی از اعداد صحیح نامنفی است.

5- حداقل در یک دنباله، دو راس متمایز وجود دارد که دارای یک درجه هستند و توجه کنید که این مطلب فقط در مورد گراف ساده برقرار است.

6- دنباله زیر از گراف $G$ مفروض است:

$d = (d_{1}, d_{2}, ....., d_{n}); d_{1} \geq d_{2} \geq .... \geq d_{n}$

به‌ازای $1 \leq k \leq n$ می‌توان درستی نامساوی زیر را ثابت کرد:

$\sum_{i = 1}^{k} d_{i} \leq k (k - 1) + \sum_{i = k + 1}^{n} \min \{k, d_{i}\}$

تمرین

گرافی رسم كنيد كه دنباله درجات راس های آن به‌صورت زیر باشد.

$(3, 3, 2, 2)$

$\begin{array}{l} \deg (a) = \deg (c) = 3 \\ \deg (b) = \deg (d) = 2 \end{array}$

تمرین

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

دنباله درجات راس های گراف شكل فوق را بنويسيد.

ابتدا درجه هر راس را می‌نویسیم:

$\begin{array}{l} \deg (a) = \deg (d) = \deg (g) = 3 \\ \deg (b) = 4, \deg (c) = 1 \\ \deg (e) = \deg (f) = 2 \end{array}$

بنابراين دنباله درجات راس های اين گراف عبارت است از:

$(4, 3, 3, 3, 2, 2, 1)$

تمرین

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

دنباله درجات راس های گراف شكل فوق را بنويسيد.

$(3, 2, 2, 1, 1, 1)$

تمرین

تعداد يال های گرافی با دنباله درجات راس های زیر را به‌دست آورید.

$(5, 3, 2, 2, 1, 1, 0)$

می‌دانيم كه مجموع جملات دنباله درجات راس های يک گراف دو برابر تعداد يال هاست.

$\begin{array}{l} \sum_{i = 1}^{p} d_{i} = 2 q \end{array}$

$\begin{array}{l} \Rightarrow 5 + 3 + 2 + 2 + 1 + 1 + 0 = 2 q \end{array}$

$\begin{array}{l} \Rightarrow q = 7 \end{array}$

دریافت مثال

دریافت فایل PDF

قضیه

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

اثبات

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

$S : d_{1}, d_{2}, ..., d_{p}$

در این‌صورت مطابق قضیه، درجات راس‌های یک گراف $\sum_{i = 1}^{p} d_{i}$ عددی زوج است.

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

تذکر

اگر گراف ساده $G$ دارای $p$ راس باشد و $p > 1$ ، حداقل دو راس دارای درجه یکسان می‌باشند و علت آن است که اگر درجه تمام راس‌ها متفاوت باشد، اجبارا دنباله درجات راس‌های گراف باید به‌صورت زیر باشند:

$S : (p - 1), (p - 2), ..., 2, 1, 0$

اما این موضوع امکان پذیر نیست، زیرا وقتی درجه یکی از راس‌ها برابر صفر باشد، یعنی $(p - 1)$ راس داریم که حداکثر درجه می‌تواند به‌صورت زیر باشد:

$[(p - 1) - 1] = p - 2$

در صورتی‌که در این دنباله حداکثر درجه $(p - 1)$ است، پس حداقل دو راس از گراف باید درجه یکسانی داشته باشند.

با توجه به موضوع فوق اگر گفته شود درجه راس‌های یک گراف تشکیل دنباله حسابی یا هندسی می‌دهند، نتیجه می‌گیریم درجه همه راس‌ها برابر است که در این حالت:

در شرایطی که دنباله درجات راس‌های یک گراف ساده، دنباله حسابی باشد، قدرنسبتش برابر صفر است.

در شرایطی که دنباله درجات راس‌های یک گراف ساده، دنباله هندسی باشد و درجه‌ها مخالف صفر باشند، قدرنسبتش $(1)$ است.

دریافت مثال

دریافت فایل PDF

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

تست شماره 1

کنکور ریاضی اردیبهشت 1403

در گراف $G$ و $|V (G)| = 8$ و $|E (G)| = 24$ است.

کمترین مقدار ممکن برای $δ (G)$ کدام است؟

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

خرید پاسخ‌ها

درجه گراف ساده

18,000تومان

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

گراف

درجه گراف ساده

تعریف درجه گراف ساده

قضایای درجه گراف ساده

دنباله‌ های درجات راس‌ ها

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

nenomatica

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

دسترسی سریع

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