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

گراف

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

آخرین ویرایش: 09 اسفند 1402

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

امتیاز:

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

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

در هر گراف ساده $G = (V, E)$ :

تعداد اعضای $V (G)$ را مرتبه $G$ می‌نامیم و با $p$ نمایش می‌دهیم، یعنی:

$p = |V (G)|$

تعداد اعضای $E (G)$ را اندازه $G$ می‌نامیم و با $q$ نمایش می‌دهیم، یعنی:

$q = |E (G)|$

تمرین

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

مرتبه و اندازه $G$ را بنویسید.

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

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

تمرین

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

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

$\{\begin{cases} p = 7 \\ q = 6 \end{cases}$

تمرین

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

$\begin{array}{l} V = \{a, b, c, d\} \\ E = \{a b, a c, a d, b c, d c\} \end{array}$

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

$\{\begin{cases} p = 4 \\ q = 5 \end{cases}$

دریافت مثال

دریافت فایل PDF

نکته

1- برای گراف ساده با $q$ یال، حداکثر مرتبه $p$ را نمی‌توان تعیین کرد زیرا به هر تعداد می‌توانیم راس از درجه صفر داشته باشیم.

2- اگر گراف ساده‌ای $q$ یال داشته باشد، حداقل تعداد راس‌های آن برابر است با:

$p \geq \frac{\sqrt{1 + 8 q}}{2}$

تمرین

آیا جمله زیر جمله درستی است؟

حداكثر مرتبه برای گرافی با $6$ يال برابر $7$ است.

خیر.

برای گراف ساده با q يال حداكثر مرتبه p را نمی‌توان تعيين كرد زيرا به هر تعداد می‌توانيم راس از درجه صفر داشته باشيم.

دریافت مثال

دریافت فایل PDF

قضایای مرتبه و اندازه گراف ساده

قضیه

هر گراف ساده که $p$ راس دارد، حداکثر تعداد یال‌هایش $(\begin{array}{l} p \\ 2 \end{array})$ و حداقل تعداد یال‌هایش صفر است:

$\{\begin{cases} 0 \leq q \leq (\begin{array}{l} p \\ 2 \end{array}) \\ 0 \leq q \leq \frac{p (p - 1)}{2} \end{cases}$

اثبات

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

چون هر یال متناظر با یک زیر مجموعه دو عضوی از راس‌ها است، پس در مورد یک مجموعه $p$ عضوی، حداکثر تعداد یال‌ها برابر است با تعداد زیرمجموعه‌های $2$ عضوی مجموعه $V (G)$ که $p$ عضو دارد.

این تعداد برابر است با تعداد انتخاب‌های $2$ شی از میان $p$ یعنی $(\begin{array}{l} p \\ 2 \end{array})$ .

یادآوری می‌کنیم که:

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

$\begin{array}{l} \Rightarrow (\begin{array}{l} p \\ 2 \end{array}) = \frac{p (p - 1)}{2!} \\ \Rightarrow (\begin{array}{l} p \\ 2 \end{array}) = \frac{p (p - 1)}{2} \end{array}$

نکته

نتایج قضیه فوق به‌شرح زیر است:

$\begin{array}{l} \max (q) = (\begin{array}{l} p \\ 2 \end{array}) = \frac{p (p - 1)}{2}; \min (q) = 0 \end{array}$

$0 \leq q \leq (\begin{array}{l} p \\ 2 \end{array}) \Rightarrow 0 \leq q \leq \frac{p (p - 1)}{2} \Rightarrow 0 \leq 2 q \leq p (p - 1)$

تمرین

گراف ساده را با مشخصات زیر در نظر بگیرید:

$\{\begin{cases} G = (V, E) \\ V = \{a, b, c, d, e\} \end{cases}$

این گراف حداقل و حداكثر چند يال دارد؟

$\{\begin{cases} \min q = 0 \\ \max q = \frac{p (p - 1)}{2} = \frac{5 (4)}{2} = 10 \end{cases}$

تمرین

حداكثر اندازه يک گراف ساده مرتبه $8$ چند است؟

$\{\begin{cases} p = 8 \\ \max q = \frac{p (p - 1)}{2} = \frac{8 (7)}{2} = 28 \end{cases}$

در ميان گراف هايی كه $66$ يال دارند، گرافی كه تعداد راس های آن كم‌ترين است، داراي چند راس است؟

اگر $q$ تعداد يال ها و $p$ تعداد راس های يک گراف باشد، آن‌گاه:

$\begin{array}{l} 0 \leq 2 q \leq p (p - 1) \end{array}$

$\begin{array}{l} \Rightarrow 0 \leq 2 \times 66 \leq p (p - 1); q = 66 \end{array}$

$\begin{array}{l} \Rightarrow p^{2} - p - 132 \geq 0 \\ \Rightarrow (p - 12) (p + 11) \geq 0 \\ \Rightarrow \{\begin{cases} p \geq 12 \\ p \leq - 11 \end{cases} \end{array}$

چون مقدار منفی برای يال و راس معنی ندارد پس $(p \leq - 11)$ قابل قبول نيست و فقط $(p \geq 12)$ قبول است، بنابراين حداقل رئوس چنين گرافی $p = 12$ است.

تمرین

گرافی با رئوس زیر را در نظر بگیرید:

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

چند گراف ساده G وجود دارد كه $q = 2$ و يكی از يال های آن $a b$ باشد؟

تعداد گراف های مورد نظر برابر است با:

$(\begin{array}{l} 4 \\ 2 \end{array}) - 1 = 6 - 1 = 5$

دریافت مثال

دریافت فایل PDF

قضیه

تعداد گراف‌های ساده با $p$ راس برابر است با:

$2^{(\begin{matrix} p \\ 2 \end{matrix})} = 2^{\frac{p (p - 1)}{2}}$

اثبات

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

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

اگر همه عضوهای $V (G)$ به‌هم متصل شده باشند، آن‌گاه $(\begin{array}{l} p \\ 2 \end{array})$ یال خواهیم داشت.

چون در گراف‌های مختلف ممکن است، هیچ یا یک یا دو یا ... یا $(\begin{array}{l} p \\ 2 \end{array})$ یال داشته باشیم، بنابراین تعداد گراف‌های مختلف برابر است با تعداد زیر‌مجموعه‌های یک مجموعه $(\begin{array}{l} p \\ 2 \end{array})$ عضوی، یعنی:

$2^{(\begin{matrix} p \\ 2 \end{matrix})} = 2^{\frac{p (p - 1)}{2}}$

تمرین

گراف های ساده با $4$ راس زیر را در نظر بگیرید. 9

$\{u, v, w, t\}$

اگر دو يال كه يكی از آنها $\{u, v\}$ باشد، تمام گراف های آن را رسم کنید.

در مجموع، تعداد زير مجموعه از اين نوع گراف داريم كه عبارتند از:

$(\begin{array}{l} 4 \\ 2 \end{array}) = 6$

$\{w, t\}, \{v, t\}, \{v, w\}, \{u, t\}, \{u, w\}, \{u, v\}$

اكنون يک يال از گراف معلوم شده كه می‌باشد.

بنابراين هريک از $5$ زير مجموعه باقيمانده را می‌توان برای يال دوم انتخاب كرد.

تمرین

چند گراف ساده G وجود دارد كه مجموعه راس های آن $4$ عضو داشته باشد؟

$p = 4$

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

$2^{(\begin{matrix} p \\ 2 \end{matrix})} = 2^{\frac{p (p - 1)}{2}} = 2^{\frac{4 \times 3}{2}} = 2^{6} = 64$

دریافت مثال

دریافت فایل PDF

خرید پاسخ‌ها

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

1,200تومان

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

گراف

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

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

قضایای مرتبه و اندازه گراف ساده

nenomatica

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

دسترسی سریع

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