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

گراف

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

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

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

امتیاز:

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

گراف‌های $P_{n}$ و $C_{n}$ و عدد احاطه‌گری

تعریف $P_{n}$

اگر $G$ گرافی از مرتبه $n \geq 1$ با راس‌های زیر باشد:

$v_{1}, v_{2}, v_{3}, \dots, v_{n}$

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

$v_{1} v_{2}, v_{2} v_{3}, v_{3} v_{4}, \dots, v_{n - 1} v_{n}$

آن‌گاه گراف $G$ را یک مسیر با $n$ راس $(P a t h)$ می‌نامند و با $P_{n}$ نشان می‌دهند.

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

عدد احاطه‌گری در گراف $P_{n}$ به‌صورت زیر محاسبه می‌شود:

$γ (P_{n}) = ⌈\frac{n}{3}⌉$

$\begin{matrix} γ (P_{1}) = ⌈\frac{1}{3}⌉ = 1 & γ (P_{2}) = ⌈\frac{2}{3}⌉ = 1 & γ (P_{3}) = ⌈\frac{3}{3}⌉ = 1 & γ (P_{4}) = ⌈\frac{4}{3}⌉ = 2 \end{matrix}$

$\begin{matrix} γ (P_{5}) = ⌈\frac{5}{3}⌉ = 2 & γ (P_{6}) = ⌈\frac{6}{3}⌉ = 2 & γ (P_{7}) = ⌈\frac{7}{3}⌉ = 3 & γ (P_{4}) = ⌈\frac{8}{3}⌉ = 3 \end{matrix}$

تعریف $C_{n}$

اگر $G$ گرافی از مرتبه $n \geq 3$ با راس‌های زیر باشد:

$v_{1}, v_{2}, v_{3}, \dots, v_{n}$

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

$v_{1} v_{2}, v_{2} v_{3}, v_{3} v_{4}, \dots, v_{n - 1} v_{n}, v_{n} v_{1}$

آن‌گاه گراف $G$ را یک دور با $n$ راس $(C y c l e)$ می‌نامند و با $C_{n}$ نشان می‌دهند.

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

عدد احاطه‌گری در گراف $C_{n}$ به‌صورت زیر محاسبه می‌شود:

$γ (C_{n}) = ⌈\frac{n}{3}⌉$

$\begin{matrix} γ (C_{3}) = ⌈\frac{3}{3}⌉ = 1 & γ (C_{4}) = ⌈\frac{4}{3}⌉ = 2 & γ (C_{5}) = ⌈\frac{5}{3}⌉ = 2 \end{matrix}$

$\begin{matrix} γ (C_{6}) = ⌈\frac{6}{3}⌉ = 2 & γ (C_{7}) = ⌈\frac{7}{3}⌉ = 3 \end{matrix}$

تمرین

گراف‌های زیر را رسم کنید و عدد احاطه‌گری هر یک را مشخص کنید.

$P_{10}$

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

$γ (P_{10}) = ⌈\frac{10}{3}⌉ = 4$

مجموعه احاطه‌گر مینیمم به‌صورت زیر معرفی می‌شود:

$\{v_{1}, v_{4}, v_{7}, v_{10}\}$

$P_{9}$

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

$γ (P_{9}) = ⌈\frac{9}{3}⌉ = 3$

مجموعه احاطه‌گر مینیمم به‌صورت زیر معرفی می‌شود:

$\{v_{2}, v_{5}, v_{8}\}$

$C_{10}$

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

$γ (C_{10}) = ⌈\frac{10}{3}⌉ = 4$

مجموعه احاطه‌گر مینیمم به‌صورت زیر معرفی می‌شود:

$\{v_{1}, v_{4}, v_{7}, v_{9}\}$

$C_{9}$

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

$γ (C_{9}) = ⌈\frac{9}{3}⌉ = 3$

مجموعه احاطه‌گر مینیمم به‌صورت زیر معرفی می‌شود:

$\{v_{2}, v_{5}, v_{8}\}$

$P_{12}$

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

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

مجموعه احاطه‌گر مینیمم به‌صورت زیر معرفی می‌شود:

$\begin{array}{l} \{v_{2}, v_{5}, v_{8}, v_{11}\} \\ γ (G) = 4 \end{array}$

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

یک مجموعه احاطه‌گر مینیمال $6$ عضوی از آن را مشخص می‌کنیم:

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

مجموعه زیر یک مجموعه احاطه‌گر مینیمال $6$ عضوی است.

$\{v_{2}, v_{4}, v_{6}, v_{8}, v_{10}, v_{12}\}$

تمرین

گرافی مشخص کنید که برای آن،عدد احاطه‌گر برابر $⌈\frac{n}{Δ + 1}⌉$ باشد.

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

$\{\begin{cases} ⌈\frac{n}{Δ + 1}⌉ = ⌈\frac{9}{2 + 1}⌉ = ⌈3⌉ = 3 \\ γ (P_{9}) = ⌈\frac{n}{3}⌉ = ⌈\frac{9}{3}⌉ = 3 \end{cases}$

$\begin{matrix} γ (P_{9}) = ⌈\frac{n}{Δ + 1}⌉ \end{matrix}$

گرافی مشخص کنید که برای آن،عدد احاطه‌گر برابر $⌈\frac{n}{Δ + 1}⌉$ نباشد.

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

مجموعه احاطه‌گر مینیمم به‌صورت زیر معرفی می‌شود:

$\{v_{2}, v_{4}, v_{6}, v_{8}, v_{11}\}$

$\{\begin{cases} γ (G) = 5 \\ ⌈\frac{n}{Δ + 1}⌉ = ⌈\frac{11}{3 + 1}⌉ = ⌈2.75⌉ = 3 \end{cases}$

$\begin{matrix} γ (G) \neq ⌈\frac{n}{Δ + 1}⌉ \end{matrix}$

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

گراف

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

گراف‌های $P_{n}$ و $C_{n}$ و عدد احاطه‌گری

تعریف $P_{n}$

تعریف $C_{n}$

nenomatica

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

دسترسی سریع

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

گراف

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

گراف‌های Pn و Cn و عدد احاطه‌گری

تعریفPn

تعریفCn

گراف‌های $P_{n}$ و $C_{n}$ و عدد احاطه‌گری

تعریف $P_{n}$

تعریف $C_{n}$