Products in Graph Theory and its properties

Graph-Theory-Research1.tex

\documentclass[12pt, a4]{article}

%% find this on: https://gist.github.com/alifa98/4fbdd935b2419b520a7a635d5e2da12a
\usepackage{amsthm,amssymb,amsmath,amsfonts}
\usepackage[top=30mm, bottom=30mm, left=25mm, right=30mm]{geometry}
\usepackage{graphicx}
\usepackage{color}
\usepackage{setspace}
\usepackage{titletoc}
\usepackage{tocloft}
\usepackage{arydshln} %% Horizontal and verical dash in matrices
\usepackage{enumitem}
\usepackage{titlesec}
\usepackage[pagebackref=false,colorlinks,linkcolor=black,citecolor=red]{hyperref}
\usepackage{xepersian}

\SepMark{-} % change step marker to dash (default is dot) 


\settextfont[Scale=1.2]{B Nazanin}
\setlatintextfont{Times New Roman}
\renewcommand{\labelitemi}{$\bullet$}

\onehalfspacing

\title{بررسی خواص ضرب‌ها در گراف}
\author{علی فرجی - 9612302}
\date{اردیبهشت 1400}

\begin{document}


\maketitle
\newpage

\tableofcontents

\newpage

\section[ضرب دکارتی]{ضرب دکارتی\LTRfootnote{Cartesian Product} }
دو گراف دل‌خواه $G$ و $H$ را در نظر می‌گیریم.
حال در مورد $G \square H$ بحث می‌کنیم.

\subsection[همبندی]{همبندی\LTRfootnote{Connectivity}}
در صورتی که یکی از گراف‌ها ناهمبند باشند حاصل ضرب نیز ناهمبند خواهد بود.
به مانند این است که هر مولفه به صورت جدا در هم ضرب می شوند و در نهایت کنار هم قرار می‌گیرند.

طبق تعریف هم می‌توانیم استدلال کنیم زیرا زمانی بین دو راسش $(u,v)$ و $(u',v')$ یالی خواهد بود که یکی از مولفه‌ها با هم برابر باشند و دیگری هم در گراف اصلی یال داشته باشد.
حال اگر یک سری راس در نظر بگیریم که مولفه‌های اولشان با هم برابر هستند و مولفه‌های دومشان هم در دو مولفه‌ی همبندی جدا باشند پس هیچ یالی بین آن رئوس نخواهد بود.

\subsection[قطر]{قطر\LTRfootnote{Diameter: $diam(G)$}}
از تعریف ضرب دکارتی روی گراف‌ها می‌دانیم که اگر مولفه‌ی دوم در راس $(u,v)$ را ثابت نگه داریم و با تغییر مولفه اول روی یال‌ها حرکت کنیم در اصل داریم روی یک کپی از گراف اول حرکت می‌کنیم و همینطور برای مولفه‌ی دوم.

فرض کنید می‌خواهیم از راس $(u,v)$ به راس $(u',v')$ برویم.
اگر $u' \ne u$ و $v' \ne v$ می‌توان با حداکثر
$Max \{diam(G), diam(H) \}$
حرکت به راسی رفت که یا $u' = u$ و یا $v' = v$ است مگر اینکه ناهمبند باشد (در این صورت قطر بینهایت است.).
حال اگر روی $G$ حرکت کرده‌ایم الان باید گراف دیگر حرکت کنیم پس می‌توانیم حداکثر با $diam(H)$ حرکت به راس مورد نظر برسیم ولی اگر ابتدا روی $H$ حرکت کرده‌ایم می‌توانیم با حداکثر $diam(G)$ به راس مورد نظر برسیم.

پس قطر در گراف حاصل‌ضرب می‌شود:

$$
diam(G \square H) = diam(H) + diam(G)
$$

\subsection[مکمل]{مکمل\LTRfootnote{Complement: $\overline{G}$ or $G^C$}}
مکمل گراف $G \square H$  را به صورت زیر بدست می‌آوریم.
روال ضرب را مانند قبل می‌رویم فقط زمانی که می‌خواهیم یال‌ها را وصل کنیم به صورت زیر عمل می‌کنیم:

اگر 
$
(u = u' \land v \nsim v' ) \lor
(v = v' \land u \nsim u') \lor
(v \ne v' \land u \ne u')
$
آنگاه $ (u,v) \sim (u',v') $

%%% TODOOOOO %%
\subsection[ماتریس مجاورت]{ماتریس مجاورت\LTRfootnote{Adjacency Matrix: $A(G)$}}
ماتریس مجاورت ضرب دکارتی به صورت زیر است:
$$
A_{G \square H} = A_1 \otimes I_{n_2} + I_{n_1} \otimes A_2
$$
 که در آن 
$|V(G)| = n_1$، 
$|V(H)| = n_2$، 
$I_n$
ماتریس همانی در اندازه $n \times n$ و عملگر $\otimes$ ضرب کرونکر\LTRfootnote{Kronecker product} ماتریس‌ها است و به صورت زیر تعریف می‌شود:
\begin{equation*}
A_{m \times n} \otimes B_{p \times q} =  
\begin{bmatrix}
a_{11} B & \cdots & a_{1n} B \\
\vdots & \ddots & \vdots  \\
a_{m1} B & \cdots & a_{mn} B \\
\end{bmatrix}_{ pm \times qn }
\end{equation*}

در اصل، در دو بخش جمع بالا،
در سمت چپ جمع با فرض ثابت نگه داشتن مولفه دوم در هر ضرب کرونکر (مثلا $a_{11} B$ )، یال‌ها در گراف اول در نظر گرفته می شود و بخش دوم ضرب هم بلعکس و با ثابت نگه داشتن اولی، یال‌ها در گراف دوم را در نظر می‌گیرد.

در اصل این دو بخش جمع به خاطر این به وجود آمده است که در دو صورت دو راس را به هم وصل می‌کنیم.
اگر در زوج مرتب:
 \begin{enumerate}
 \item
مولفه اول یکسان و مولفه های دوم با هم همسایه باشند در گراف دوم
\item
اگر مولفه دوم یکسان و مولفه‌های اول با هم همسایه باشند در گراف اول
 \end{enumerate}

\subsection[عدد خوشه‌ای]{عدد خوشه‌ای\LTRfootnote{Clique Number: $\omega(G)$}}
وقتی دو گراف را در هم ضرب می‌کنیم در اصل خوشه آن‌ها هم در هم ضرب می‌شود.

ضرب دکارتی دو گراف کامل یک گراف کامل ایجاد نمی‌کند.
چون اگر هر دو گراف کامل $n > 1$ راس داشته باشد می‌توان 2 راس در رئوس گراف ضرب دکارتی به صورت $(a,b)$ و $(c,d)$ مشخص کرد که $a \ne c$ و $b \ne d$ باشد و به وضوح بین این‌ها یالی نخواهد بود.

بقیه رئوس گراف هم که شامل خوشه نیست هم نمی‌تواند خوشه تشکیل دهد به مانند استدلال بالا.
لذا خوشه‌های موجود در گراف حاصل‌ضرب همان خوشه‌های موجود در گراف‌های اولیه است که تکرار شده‌اند.
پس:
$$
\omega(G \square H) = max\{ \omega(G), \omega(H) \}
$$


\subsection[عدد استقلال]{عدد استقلال\LTRfootnote{Independent Number: $\alpha(G)$}}
با توجه به مطالب بررسی شده عدد استقلال ضرب کارتزین دو گراف به راحتی قابل محاسبه نیست ولی 
\lr{Vizing, V. G.}
نشان داد که عدد استقلال در نامساوی زیر صدق می‌کند:
\begin{align*}
\alpha(G).\alpha(H) + min\left\{ |V(G)|-\alpha(G),|V(H)|-\alpha(H) \right\} & \\ 
\leq \alpha(G \square H) \leq \\
min\left\{ \alpha(G).|V(H)|, \alpha(H).|V(G)| \right\}
\end{align*}

\subsection{خواص دیگر}

\subsubsection{خاصیت جابجایی}
با توجه به متقارن بودن تعریف این ضرب خاصیت جابجایی دارد. یعنی $G \square H \cong H \square G$ است.


\section[ضرب کرونایی]{ضرب کرونایی\LTRfootnote{Corona Product} }
دو گراف دل‌خواه $G$ و $H$ را در نظر می‌گیریم.
حال در مورد $G \odot H$ بحث می‌کنیم.

\subsection{همبندی}
چهار حالت برای همبندی گراف‌های $G$ و $H$ فرض می‌کنیم:
\begin{enumerate}
\item
هر دو همبند
\item
$G$ همبند و $H$ ناهمبند
\item
$G$ ناهمبند و $H$ همبند
\item
هر دو ناهمبند
\end{enumerate}

\subsubsection{هر دو همبند}
اگر هر دو همبند باشد با توجه به اینکه همه رئوس $H_i$ها به یکی از راس های $G$ وصل خواهد شد و خود گراف $G$ هم همبند است پس بین همه رئوس گراف حاصل‌ضرب می‌توان مسیری پیدا‌ کرد، پس همبند خواهد بود.
\subsubsection{$G$ همبند و $H$ ناهمبند}
همه رئوس گراف $H_i$ها به یکی از رئوس گراف $G$ وصل خواهد شد پس اگر $G$ همبند باشد عملا همه رئوس، مسیری بین هم خواهند داشت. مثلا برای حرکت در درون $H_i$ اول به گراف $G$ می‌رویم سپس به درون $H_i$ باز می‌گردیم. (و می‌دانیم که $G$ همبند است و از $G$ به همه رئوس در همه $H_i$ها حتما یالی وجود دارد.)

\subsubsection{$G$ ناهمبند و $H$ همبند}
در این صورت گراف حاصل ناهمبند خواهد شد.
زیرا خود گراف $G$ تکرار می‌شود و می‌دانیم که $H_i$ها هم بدون واسطه $G$ به هم مسیری ندارند پس گراف حاصل دقیقا به اندازه تعداد مولفه‌های همبندی $G$ مولفه همبندی خواهد داشت.
\subsubsection{هر دو ناهمبند}
مانند استدلال قبلی که $G$ ناهمبند است در این صورت این نیز ناهمبند خواهد بود. (زیرا در استدلال قبلی هیچ استفاده ای از همبندی $H_i$ها نشده)

\subsection{قطر}
فرض می‌کنیم که $G$ همبند باشد زیرا در این صورت قطر بی‌نهایت خواهد شد.

فرض کنید می‌خواهیم مسیرهای درون یک  $H_i$ را در نظر بگیریم.
می‌دانیم که می‌توانیم ابتدا به راس متناظر این  $H_i$ در  $G$ برویم و دوباره به هر راسی که می‌خواهیم برگردیم پس حداکثر فاصله در درون هر $H_i$ 2 است.

حال فرض کنید میخواهیم از $H_i$ به یک راس در درون $G$ برویم که با یک حرکت به خود گراف $G$ می‌رسیم (راس متناظر برای $H_i$  در $G$)
حال در درون $G$ ممکن است به اندازه $diam(G)$ حرکت کنیم. پس حداکثر با $diam(G) +1 $ به راس مورد نظر می‌رسیم.

حال فرض کنید می‌خواهیم بین $H_i$ و $H_j$  که $i \ne j$ است حرکت کنیم طبق استدلال‌های قبلی برای حرکت از $H_i$ به راس متناظر $H_j$ در گراف $G$ باید حداکثر $diam(G) +1$ گام برداریم حال با یک گام دیگر به راس درون $H_j$ می‌رسیم.

پس در حالت کلی داریم:
$$
diam(G \odot H) = diam(G)+2
$$

\subsection{مکمل}
فرض می‌کنیم که $|V(G)| = n$  و $|V(H)| = m$ و مکمل حاصل‌ضرب $G \odot H$ را بدست می‌آوریم:
\begin{enumerate}
\item
ابتدا یک $\overline{G}$ قرار می‌دهیم و $\overline{H_i}$ها را اطراف آن قرار می‌دهیم.
\item
حال مانند حالت ضرب عادی برای هر $\overline{H_i}$ یک راس در $\overline{G}$ در نظر می‌گیریم.
\item
همه راس های $\overline{H_i}$ را به همه راس‌های  $\overline{G}$ وصل می‌کنیم بجز راسی که در مرحله قبل برای آن در نظر گرفتیم.
\item
همه‌ی راس‌های همه‌ی $\overline{H_i}$ها باید به هم وصل باشند یعنی یک راس در $\overline{H_1}$ باید به همه رئوس $\overline{H_2}$ وصل باشد و برعکس.
\end{enumerate}

خیلی شلوغ می شود، تعداد رئوس و تعداد یال‌ها:
\begin{align*}
|V(\overline{G \odot H})| &= n*m + n \\
|E(\overline{G \odot H})| 	&= \frac{(n*m + n) * (n*m + n - 1)}{2} - (|E(G)| + n * |E(H)| + n*m) \\
\end{align*}

\subsection{ماتریس مجاورت}
فرض می‌کنیم که $|V(G)| = n$  و $|V(H)| = m$ باشد.

باتوجه به تعریف ضرب کرونایی، ماتریس $A(G \odot H)$ به صورت زیر می‌باشد:

\begin{equation*}
\bordermatrix{
          &V(G) & V(H_1) & V(H_2) & \cdots & V(H_n)  \cr 
          V(G) & A(G)_{n \times n}  & \begin{bmatrix} \begin{matrix} 1 & 1 & \cdots & 1 \end{matrix} \\ \text{\huge\lr{0}} \end{bmatrix}_{n \times m} & \begin{bmatrix} \begin{matrix} 0 & 0 & \cdots & 0 \\ 1 & 1 & \cdots & 1 \end{matrix} \\ \text{\huge\lr{0}} \end{bmatrix}_{n \times m}  & \cdots & \begin{bmatrix} \text{\huge\lr{0}} \\ \begin{matrix} 1 & 1 & \cdots & 1 \end{matrix} \end{bmatrix}_{n \times m}  \cr
          V(H_1) & \begin{bmatrix} \begin{matrix} 1 \\ 1 \\ \vdots \\ 1 \end{matrix} & \text{\huge\lr{0}} \end{bmatrix}_{m \times n}  & A(H)_{m \times m} & \text{\huge\lr{0}}_{m \times m} & \cdots & \text{\huge\lr{0}}_{m \times m} \cr
          V(H_2) & \begin{bmatrix} \begin{matrix} 0 & 1 \\ 0 & 1 \\ \vdots & \vdots \\ 0 & 1 \end{matrix} & \text{\huge\lr{0}} \end{bmatrix}_{m \times n} & \text{\huge\lr{0}}_{m \times m} & A(H)_{m \times m} & \cdots & \text{\huge\lr{0}}_{m \times m} \cr
          \vdots & \vdots & \vdots & \vdots & \ddots & \vdots  \cr
          V(H_n) & \begin{bmatrix} \text{\huge\lr{0}} & \begin{matrix} 1 \\ 1 \\ \vdots \\ 1 \end{matrix} \end{bmatrix}_{m \times n} & \text{\huge\lr{0}}_{m \times m} & \text{\huge\lr{0}}_{m \times m} & \cdots & A(H)_{m \times m} }
\end{equation*}

روی قطر اصلی ماتریس بزرگ در اصل همان رئوس ببین خود $H_i$ها و خود $G$ است. درایه‌های دیگر هم به این علت است که مثلا راس اول در $G$ با کل رئوس گراف $H_1$ یال دارد و ...

\subsection{عدد خوشه‌ای}
با توجه به اینکه از $H$ به تعداد رئوس $G$ کپی می‌گیریم و وصل می‌کنیم اگر خوشه در گراف $H$ باشد آنگاه یک راس به آن خوشه اضافه می‌شود و 
$$
\omega(G \odot H) = \omega(H) + 1
$$
چون یک راس به کپی‌های $H_i$ اضافه می‌شود که به همه رئوس آن وصل است.

ولی اگر خوشه در $G$ باشد آنگاه به آن راسی اضافه نمی‌شود که به همه رئوس $G$ وصل باشد و داریم:
$$
\omega(G \odot H) = \omega(G)
$$

پس در نتیجه در حالت کلی داریم:
$$
\omega(G \odot H) = Max\{\omega(G), \omega(H) + 1\}
$$

\subsection{عدد استقلال}
فرض می‌کنیم که $|V(G)| = n$ باشد.
می‌دانیم که از $H$ به تعداد $n$ بار کپی می‌کنیم و در گراف حاصل‌ضرب قرار می‌دهیم و همه رئوس آن را به گراف $G$ وصل می‌کنیم.

با توجه به نکته‌ی قبلی ما اگر راسی از $G$ انتخاب کنیم دیگر نمی‌توانیم از $H_i$ متناظر متصل به آن، راسی را در مجموعه مستقل بیاوریم و از طرفی می‌دانیم که کمترین میزان $\alpha$ برای یک گراف برابر 1 است (مگر اینکه اصلا راسی نداشته باشد) پس ما هیچ گاه راسی از $G$ در مجموعه مستقل راسی نمی‌آوریم چون اگر انتخاب کنیم دیگر از گراف $H_i$ آن نمی‌توانیم راسی برداریم در حالی که اگر انتخابش نکنیم ما حتما از $H_i$ حداقلا یک راس را برای مجموعه مستقل راسی برمی‌داریم.

چون همه $H_i$ها همگی جدا از هم هستند و اصلا یالی بین آنها نیست و از $G$ هم راسی بر نمی‌داریم پس هر مجموعه مستقل راستی در $H_i$ها را می‌توانیم به مجموعه مستقل راسی کلی اضافه کنیم.

پس داریم:
$$
\alpha(G \odot H) = n * \alpha(H)
$$

\subsection[عدد پوشش راسی]{عدد پوشش راسی\LTRfootnote{Vertex Cover Numver: $\tau(G)$}}
فرض می‌کنیم که $|V(G)| = n$  و $|V(H)| = m$ باشد.

از قضیه‌ی گالای استفاده می‌کنیم:
\begin{align*}
\tau(G \odot H) 	& = |V(G \odot H)| - \alpha(G \odot H) \\
 				& =  (n * m) + n  - \alpha(G \odot H) \\
 				& = (n * m) + n  - n * \alpha(H) \\
 				& = n * (m + 1 - \alpha(H)) \\
 				& = n * (\overbrace{m - \alpha(H)}^{\tau(H)} + 1 ) \\
 				& = n * (\tau(H) + 1 ) \\
\end{align*}


{
\tiny
این فایل به کمک \lr{\XeTeX} توسط علی فرجی ساخته شده است.
برای مشاهده سورس کد به آدرس \lr{https://gist.github.com/alifa98/4fbdd935b2419b520a7a635d5e2da12a} مراجعه کنید.
}
\end{document}