\chapter*{مقدمه}

مطالعه روی ترید‌های گرافی به عنوان یک تعمیم از ترید‌ها در طرح‌ها به وجود آمد. مفهوم ترید در طرح‌ها اولین بار توسط هدایت
\LTRfootnote{Hedayat}
درسال 1960 مطرح شد
\cite{hedayat}
 .یک
$(v,k,t)$
ترید از حجم
$s$
با زوج
$\lbrace T_1, T_2 \rbrace$
تعریف می‌شود که
$T_1$
،
$T_2$
دو خانواده مجزا از
$s$
بلوک از اندازه 
$k$
هستند که از یک 
$v$
مجموعه ثابت انتخاب شده اند به طوری که هر
$t$
تایی از 
$v$
مجموعه در تعداد یکسانی از بلوک‌های 
$T_1$
و
$T_2$
ظاهر شود.
بیلینگتن 
\LTRfootnote{Billingtone}
و هافمن
\LTRfootnote{Hoffman}
در
\cite{TG}
مسأله ترید را به بحث ترید در گراف‌های ساده تعمیم دادند.

یک اشتاینر ترید با
$t=2$
، را به آسانی می‌توان به نظریه گراف‌ها مربوط کرد. بنیان یک مجموعه از
$v$
رأس و بلوک‌ها گراف‌های کامل از اندازه 
$k$
روی مجموعه بنیان هستند و مجموعه‌های 
$t=2$
عضوی، یال‌ها هستند. اجتماع بلوک‌ها در
$T_1$
که برابر با اجتماع بلوک‌ها در
$T_2$
نیز است، گراف ساده 
$H$
روی 
$v$
رأس است. بنابراین یک  
$(v,k,2)$
اشتاینر ترید از حجم 
$s$
معادل با دو تجزیه مجزا از گراف ساده
$H$
روی 
$v$
رأس به 
$s$
کپی از
$K_k$
است.

 در
\cite{TG}
مفهوم ترید‌های گرافی به حالتی که بلوک‌ها لازم نیست گراف کامل باشند تعمیم یافته‌است. که در این حالت باید، هر بلوک با یک گراف ساده 
$G$
یکریخت باشد، و در این حالت می‌گوییم یک (اشتاینر)
$-G$
ترید از حجم
$s$
و بنیان
$v$
وجود دارد. در حقیقت اندازه بنیان در کار‌های اولیه روی تریدهای گرافی در
\cite{TG}
و
\cite{parti Bil}
و
\cite{parti jame}
نادیده گرفته شده‌است، و تنها به حجم ترید بدون اشاره‌ای به بنیان ترید پرداخته‌اند.

نتایج مختلفی در
\cite{TG}
بدست آمده‌است، به ویژه لم 
\ref{tg2.2}
که طبق آن اگر
$G$
شامل یک مجموعه از رأس‌های مستقل باشد به طوری که حذف این رأس‌ها و یال‌های متصل به آن‌ها 
$G$
را ناهمبند سازد، آنگاه
$-G$
ترید‌هایی از حجم‌های بیشتر یا مساوی 
$2$
وجود خواهد داشت( این شرط کافی است و لازم نیست). 

حجم ترید‌های مجاز وقتی که
$G$
یک گراف چندبخشی کامل دلخواه باشد در
\cite{parti jame}
و
\cite{parti Bil}
بدست آمده؛ 

برای هر گراف چند بخشی کامل  
$G$
مجموعه حجم‌های ممنوع ترید زیرمجموعه‌ای از 
$\lbrace 1,2,3,4,5 \rbrace$
است. بنابراین خانواده بزرگی از گراف‌های غیر کامل وجود دارد که تنها تعداد کمی از اعداد در مجموعه‌ی حجم‌های ممنوع آن هستند و این تعداد متناسب با مرتبه 
$G$
افزایش پیدا نمی‌کند و این با حالتی که 
$G$
گراف کامل است در تضاد است. زیرا طبق لم
\ref{tg4.1}
 حجم‌های ممنوع ترید برای گراف کامل با مرتبه گراف افزایش پیدا می‌کند. اگرچه در
 \cite{random}
 نشان داده‌شده‌است برای گراف‌های تصادفی از مرتبه
 $k$
 (که در آن هر یال با احتمال
 $\frac{1}{2}$
 واقع می‌شود)، تعداد حجم های ممنوع ترید به نسبت
 $\frac{k}{log\,k}$
 افزایش پیدا می‌کند. بنابراین گراف‌های کامل و گراف‌های تصادفی تنها گراف‌های شناخته شده با این خاصیت هستند.
 
یافتن یک دسته‌بندی کامل از گراف‌های که مجموعه حجم‌های ممنوع ترید برای آن
$\{1\}$
یا
$\{1,2\}$
است، باقی مانده‌است. و همچنان حل نشده‌است، اگر چه احتمالاً یک مسأله خیلی سخت است. 

 کار‌های بعدی روی ترید‌ها در گراف، روی محدوده حجم ترید‌های اشتاینری ممکن، برای بنیان ثابت
$v$
بحث می‌کند. مسأله طیف ترید برای دورهایی از طول سه
$(K_3)$
\cite{C3}
، چهار
\cite{C4}
، پنج
 \cite{C5}
 و شش
 \cite{C6}
 و گراف 
 $K_4-e$
 \cite{K4-e}
  و گراف‌های ستاره‌ای
  \cite{star}
  حل شده است.
  
تمام دور‌ها از طول چهار یا بیشتر شامل یک جفت از رأس‌های مستقل هستند که با حذف آن‌ها یک گراف ناهمند باقی می‌ماند، پس طبق لم
\ref{tg2.2}
، مشخص شده است که، برای این گراف‌ها 
$-G$
ترید‌هایی از هر حجم  بیشتر یا مساوی دو وجود دارد.
برای چنین گراف‌هایی در نظر گرفتن این سوال جالب توجه‌تر است که برای هر اندازه بنیان چه حجم ترید‌هایی مجاز هستند؟

چون در این پایان‌نامه، ترید‌ها اشتاینری هستند، برای هریک از دورها به طول سه، چهار، پنج و شش یک کران بالا روی حجم ترید با بنیان
$v$
با استفاده از تعداد دور‌های
$C_3$
،
$C_4$
،
$C_5$
یا
$C_6$
در یک ماکسیم بسته بندی از گراف
$K_v$
با این دور‌ها، بدست می‌آید.نتایج وجودی برای گراف‌های
$C_3$
و
$C_5$
را با استفاده از دو مسأله اشتراک که قبلاً حل شده‌است بررسی می‌کنیم؛ مسأله اشتراک ماکسیمم بسته بندی و اشتراک 
$GDD$
ها برای
$C_3$
و
$C_5$.

در این پایان‌نامه، در  فصل دوم طیف تریدها را برای چند خانواده از گراف‌ها بررسی می‌کنیم.

در فصل سوم یک مرور کوتاهی بر مسأله وجود 
$-G$
طرح‌ها انجام می‌دهیم.

بعد در ادامه در مورد شرایط وجود
$-G$
طرح متعادل صحبت می‌کنیم و سپس برای نمونه یک 
$\textsc{4-kite}$
 طرح متعادل را ارائه می‌نماییم.

در فصل آخر نیز ارتباط بین 
$-G$
طرح‌ها و 
$-G$
ترید‌ها و طرح‌های بلوکی بیان می‌شود.

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

ترید‌های گرافی که اشتاینری نیستند هنوز بررسی نشده‌اند. در این حالت ترید می‌تواند هنوز یک ترید ساده باشد( هیچ تکراری در
$T_1$
و 
$T_2$
ندارد) که گراف
$G$
همچنین ساده است، اما گراف 
$H= \bigcup G_i$
که
$G_i \in T_1$
است، ساده نیست، پس ترید اشتاینری نیست.

تریدهای گرافی چندگانه نیز هنوز بررسی نشده اند. در این حالت به جای دو خانواده از بلوک‌ها، 
$\mu$
خانواده از بلوک‌ها خواهیم داشت به‌گونه‌ای که هر دوتا از آن‌ها تشکیل یک ترید دهند.

در این پایان‌نامه، 

گراف
  $K_n$
  روی مجموعه رأس‌
$\lbrace a_i \vert\; 1 \leq i \leq n \rbrace$
  و مجموعه یال
  $\lbrace a_ia_j \vert\; 1 \leq i,j \leq n, i \neq j \rbrace$
  را با
  $a_1a_2\ldots a_n$
  نشان می‌دهیم.
  
  گراف
  $C_n$
  روی مجموعه رأس‌
$\lbrace a_i \vert\; 1 \leq i \leq n \rbrace$
  و مجموعه یال
  $\lbrace a_ia_{i+1} \vert\; 1 \leq i \leq n\rbrace$
  را با
  $(a_1,a_2,\ldots, a_n)$
  نشان می‌دهیم.
  
  گراف 
 $K_4-e$
 با رأس‌های
 $\{a,b,c,d\}$
 و تمام یال‌های بین هر دو رأس به جز یال
 $cd$
 را با
 $[a,b,c - d]$
 نشان می‌دهیم.
 
 گراف
$K_{1,x}$
  روی مجموعه رأس‌
$\lbrace a_i \vert\; 0 \leq i \leq x \rbrace$
  و مجموعه یال
  $\lbrace a_0a_i \vert\; 1 \leq i \leq x\rbrace$
  را با
  $[a_0 : a_1,a_2,a_3,\ldots ,a_x]$
  نشان می‌دهیم.

 گراف
$P_3$
  روی مجموعه رأس‌
$\lbrace a_1 ,a_2,a_3 \rbrace$
  و مجموعه یال
  $\lbrace a_1a_2, a_2a_3\rbrace$
  را با
  $[ a_1,a_2,a_3]$
  نشان می‌دهیم.