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

گراف

نمایش ماتریسی گراف ساده

آخرین ویرایش: 18 فروردين 1402

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

امتیاز:

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

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

ماتریس مجاورت گراف ساده $G = (V, E)$ از مرتبه $p$ که با نماد $A (G)$ نمایش داده می‌شود، عبارت است از $A(G)= {[a_{ij}]}_{p×p}$ به‌طوری‌که:

$a_{ij} = \{\begin{cases} {1 ; V}_{i} V_{j} \in E(G) \\ {0 ; V}_{i} V_{j} \notin E(G) \end{cases}$

تمرین

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

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

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

$A(G)= [\begin{array}{l} 0 1 0 1 0 \\ 1 0 0 1 1 \\ 0 0 0 1 1 \\ 1 1 1 0 1 \\ 0 1 1 1 0 \end{array}]$

همان‌طور که مشاهده می‌شود، تمام درایه‌های این ماتریس $0$ و $1$ است.

درایه $a_{i j}$ از ماتریس را برابر $1$ می‌گیریم اگر $V_{i}$ و $V_{j}$ را یالی به‌هم وصل کرده باشد، یعنی $V_{i} V_{j} \in E(G)$ در غیر این‌صورت درایه $a_{i j}$ عدد $0$ است.

در گراف فوق چون $V_{4}$ و $V_{5}$ به‌وسیله یالی به‌هم متصل شده‌اند $a_{45} = 1$ است. (سطر چهارم و ستون پنجم)

تمرین

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

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

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

$A(G) = [\begin{matrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 \end{matrix}]$

دریافت مثال

دریافت فایل PDF

نکته

ویژگی‌های ماتریس مجاورت یک گراف ساده

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

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

ماتریس مجاورت این گراف ساده به شکل زیر است:

$A(G)= {[\begin{matrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{matrix}]}_{4×4}$

1- ماتریس $A$ مربعی است.

2- درایه‌های روی قطر اصلی $A$ همگی صفرند، زیرا هیچ راسی با خودش مجاور نیست یعنی در گراف ساده طوقه نداریم.

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

3- هر درایه ماتریس $A$ برابر صفر یا یک است.

4-ماتریس $A$ متقارن است یعنی $a_{ij} {=a}_{ji}$

5- تعداد یک‌های ماتریس، برابر با تعداد درجه‌های راس‌های این گراف است و برابر $(2 q)$ می‌باشد.

6- تعداد یک‌های یک سطر (یا یک ستون) برابر با درجه راس مربوط به آن سطر (یا ستون) است.

7- مرتبه ماتریس مجاورت، با مرتبه گراف یعنی $(p)$ برابر است.

8- نصف تعداد یک‌ها برابر است با تعداد یال‌های $(q)$ .

9- تعداد درایه‌های $(1)$ در ماتریس مجاورت یک گراف ساده از مرتبه $(p)$ و اندازه $(q)$ را برابر $(2 q)$ و لذا تعداد درایه‌های صفر برابر $p^{2} -2q$ است.

دریافت مثال

دریافت فایل PDF

قضایای ماتریس مجاورت

قضیه

تعداد یک‌های یک سطر (یا یک ستون) برابر با درجه راس مربوط به آن سطر (یا ستون) است.

اثبات

اگر $A$ ماتریس مجاورت گراف ساده $G = (V, E)$ باشد، هر عدد یک که در سطر $i$ ام (یا ستون $i$ ام) $A$ ظاهر شود که $(1 \leq i \leq p)$ نشان‌گر آن است که از راس $V_{i}$ (راس متناظر همان سطر یا ستون) یک یال عبور کرده، بنابراین تعداد $(1)$ های سطر $i$ ام (یا ستون $i$ ام) برابر تعداد یال‌هایی است که از راس $V_{i}$ عبور می کند، بنابراین این تعداد این $(1)$ ها درجه راس $V_{i}$ می‌باشد.

دریافت مثال

دریافت فایل PDF

قضیه

اگر $A$ ماتریس مجاورت گراف ساده $G = (V, E)$ از مرتبه $p$ باشد، هر درایه واقع بر قطر اصلی ماتریس $A^{2}$ برابر است با درجه راس متناظر سطر (یا ستون) درایه مزبور

به‌عبارت دیگر، اگر $V_{i} \in V(G)$ باشد، آن‌گاه در درایه سطر $i$ ام و ستون $i$ ام ماتریس:

${deg(V}_{i} {)=A}^{2}$

اثبات

چون $A$ متقارن است، بنابراین $a_{ij} {=a}_{ji}$ .

درایه سطر $i$ ام و ستون $i$ ام از $A^{2}$ مطابق زیر به‌دست می‌آید:

$a_{i1} a_{1i} {+a}_{i2} a_{2i} + ... {+a}_{ip} a_{pi} {=a}_{i1} {.a}_{i1} {++a}_{i2} a_{i2} + ... {+a}_{ip} a_{ip} {=a}^{2}_{i1} {+a}^{2}_{i2} + ... {+a}^{2}_{ip}$

می‌دانیم تعداد یک‌های موجود در سطر $i$ ام $A$ برابر درجه راس $V_{i}$ می‌باشد، چون $i^{2} = 1$ بنابراین حاصل فوق همان درجه راس $V_{i}$ است.

نکته

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

مجموع درایه‌های قطر اصلی $A^{2}$ :

$q(G)= \frac{1}{2}$

دریافت مثال

دریافت فایل PDF

قضیه

فرض کنید $A$ ماتریس مجاورت گراف $G$ با $p$ راس باشد که در آن $p > 1$ است، در این‌صورت درایه $i j$ ام ماتریس $A^{n}$ تعداد مسیرهای به‌طول $n$ از راس $V_{i}$ به راس $V_{j}$ است.

ماتریس وقوع گراف ساده

فرض کنید $M= {[m_{ij}]}_{p×q}$ یک ماتریس $p \times q$ باشد که به‌صورت زیر تعریف شده است:

$m_{ij} = \{\begin{cases} 1 \\ 0 \end{cases}$

$(1)$ وقتی در نظر گرفته می‌شود که راس $v_{i}$ روی یال $e_{j}$ واقع شده باشد.

در غیر این صورت $(0)$ را در نظر می‌گیریم.

آن‌گاه $M$ را ماتریس وقوع $G$ نامیده می‌شود.

از آنجا که گراف $G$ دارای $p$ راس و $q$ یال است، از این رو ماتریس وقوع $M$ یک ماتریس $p \times q$ است.

دریافت مثال

دریافت فایل PDF

ساختار مجاورت (پیوندی) گراف ساده

سوال

فرض کنید $G$ یک گراف با $p$ راس باشد، دو عیب اساسی ذخیره در حافظه کامپیوتر را به‌صورت ماتریس مجاورت توضیح دهید؟

عیب اول) اگر خواسته باشیم مجموعه راس‌ها و یا مجموعه یال‌ها را تغییر دهیم، ممکن است انجام تغییرات مورد نظر روی $A (G)$ مشکل باشد.

عیب دوم) ممکن است ماتریس $A$ یک ماتریس خلوت باشد (که حاوی تعداد بسیار زیادی صفر است) از این رو، وقتی $A$ در حافظه کامپیوتر ذخیره می شود، مقدار زیادی از حافظه بدون معرف رها می‌شود.

بنابراین، معمولا ماتریس $A (G)$ به‌صورت نمایش ساختار مجاورت یا پیوندی در حافظه کامپیوتر ذخیره می‌شود که به بحث آن می‌پردازیم.

تعریف

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

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

می‌خواهیم نمایش ساختار مجاورت یا نمایش پیوندی یک گراف را با استفاده از گراف $G$ که به‌صورت زیر رسم شده، تعریف کنیم.

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

پس از هر راس $V_{i}$ از گراف $G$ در نمایش ساختار مجاورت گراف $G$ مجموعه راس‌های مجاور آن نوشته می‌شود، چنین نمایشی ممکن است مانند جدول فوق به‌صورت فشرده زیر نشان داده شود:

$G = \{(A:B,P); (B:A,C,P,Q); (C:B); (P: A,B); (Q :B)\}$

ملاحظه می‌کنید که کالن $(:)$ یک راس را از لیست راس‌های مجاور آن جدا می‌کند و سمی‌کالن $(;)$ لیست‌های مختلف را از هم جدا می‌کند.

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

دریافت مثال

دریافت فایل PDF

خرید پاسخ‌ها

نمایش ماتریسی گراف ساده

6,000تومان

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

گراف

نمایش ماتریسی گراف ساده

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

قضایای ماتریس مجاورت

ماتریس وقوع گراف ساده

ساختار مجاورت (پیوندی) گراف ساده

سوال

تعریف

nenomatica

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

دسترسی سریع

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