چکیده

شاخص وینر گراف G به صورت مجموع فواصل بین همه جفت از رئوس تعریف میشود.

شاخص وینر یک ویژگی جالب از ریاضی شیمی است. شاخص سگد(( )Sz G) تعمیمی از شاخص وینر برای همه گرافهای همبند میباشد. درمورد درختها شاخص سگد با شاخص وینر برابر است.

از اینرو هر تحقیقی در شاخص سگد معنیدار است اگر و فقط اگر برای گرافهای شامل دور به کار برده شود. در محاسبه شاخص سگد ،برای ( )e  uv E G تعداد رئوس با فاصلههای یکسان از u و v در نظر گرفته نمیشود. به همین دلیل برای شمردن این تعداد رئوس، شاخص سگد اصلاح شده (شاخص سگد ستاره (( )*Sz G)) تعریف شده است. فرض کنید G گراف همبند و

( )η(G ) Sz G( ) W G . یک نتیجه معروف از کلاوزار، راجاپکس و گوتمن نشان میدهد که

(G) و بنا به نتیجهای از دوبرینین و گوتمن ،(G) است اگر و فقط اگر بلوکهایG  کامل باشند. کارمان را با طبقه بندی گرافهای همبند که بیان میکند ,4 5(G) ، ادامه داده و سرانجام بیان نمودهایم که برای یک عدد صحیح مثبت ,13k گراف G وجود دارد به طوریکه (G)  k.   

گراف نسر (, )KG m n گرافی است که رئوس آن زیرمجموعههای n عضوی از یک مجموعه m عضوی هستند و دو راس مجاورند هرگاه مجموعههای متناظر، مجزا باشند. در این قسمت شاخص سگد و وینر گراف نسر را به وضوح محاسبه میکنیم. 

واژههای کلیدی. شاخص وینر، شاخص سگد، شاخص سگد اصلاح شده، گراف نسر، عدد رنگی.

فهرست مطالب

عنوان                                                                                                                                       صفحه

فصل اول. تعاریف و مفاهیم اساسی 

1-1 مقدمه………………………………………………………………………………………………. 2

1-2 تعاریف و مفاهیم اساسی…………………………………………………………………………… 2

فصل دوم: شاخصهای سگد و وینر

2-1 شاخص سگد و وینر برای گرافهای حاصلضربی و ترکیبی……………………………………….14 

٢-2 شاخص وینر چند گراف…………………………………………………………………………………..…….19

2-3 کرانها در شاخص سگد…………………………………………………………………………………………23

2-4 رابطهی شاخص سگد گراف با مکمل آن…………………………………………………………………..26

2-5 گرافهایی با شاخص سگد مینیمال………………………………………………………………………….29  

26 گرافهایی با شاخص سگد ماکسیمال ……………………………………………………………………… °٣

فصل سوم. شاخص سگد اصلاح شده 

3-1 ارتباط شاخص سگد با شاخص سگد اصلاح شده……………………………………………………..39

3-2 کرانهایی برای شاخص سگد اصلاح شده ………………………………………………………………..43

3-3 گرافهای تک دور با کوچکترین شاخص سگد اصلاح شده………………………………………48

3-4 گرافهای تک دور با بزرگترین شاخص سگد اصلاح شده………………………………………….52

3-5 گرافهای دو دور با شاخص سگد اصلاح شده ماکسیمال…………………………………………..59

فهرست فصل چهارم:گرافهای نسر

4-1 قطر گراف نسر………………………………………………………………………………………………………65 

4-2 عدد رنگی گراف نسر……………………………………………………………………………………………………………………68

4-3 عدد وینر گراف نسر …………………………………………………………………………………………….. 69

4-4 عدد وینر گرافهای فرد………………………………………………………………………………………… 77

4-5 شاخص سگد گراف نسر………………………………………………………………………………………. ٧٩

4-6 اختلاف شاخص وینر و شاخص سگد………………………………………………………………………84

فهرست شخصیتهای متن پایان نامه………………………………………………………………………………97.

منابع و مآخذ………………………………………………………………………………………………………………. 98

فهرست جداول

جدول 4 -1- مقدارهای η(H) برای گرافهای دو-همبند با 5 راس………………………………………96

فهرست شکل ها 

شکل 1-1 یالها و راسهای برشی یک گراف…………………………………………………….4

شکل 1-2 گراف نسر ( ,5 2)KG……………..ا……………………………………………………….°1

شکل 2-1 گرافهای دو دور B n.………….ا……………………………………………………….37

شکل 3-1 گراف نامنتظم انتقال منظم……………………………………………………………….. °4

شکل 3-2 دو گراف دو بخشی انتقال منظم با انتقالهای متفاوت……………………………43

شکل3-3 گرافهای همبند منتظم با 12 راس که انتقال منظم نیستند……………………..43

شکل 3-4-الف. (S t tn ( 1 2, ,…,tr  و ب. (Sn r,  Sn (t t1 2, ,…,tr . …………..ا…………….48

شکل 4-1 گرافهایA  و B …………ا……………………………………………………………..86

شکل 4-2 گرافهای 5- راسی……………………………………………………………………….96

شکل 4-3 گرافهای 3 ,2 ,1L L L……………ا……………………………………………………96

فهرست علائم و اختصارات

مجموعه یالها………………………………………………………………………………………..( )E G

مجموعه راسها……………………………………………………………………………………… ( )V G

درجه راس………………………………………………………………………………………….deg(v )

قطر گراف……………………………………………………………………………………………………..d

مکمل گراف ………………………………………………………………………………………………..G 

یال گراف m……………………………………………………………………………………………… G

تابع فاصله …………………………………………………………………………………………..d uv,

عدد رنگی …………………………………………………………………………………………….χ(G )

زیرگراف ایزومتریک……………………………………………………………………………H G

تعداد مثلثهای گراف……………………………………………………………………………..t(G )

شاخص زاگرب…………………………………………………………………………………………..1M

  یکریختی دو گراف………………………………………………………………………………..G H

خروج از مرکز راس………………………………………………………………………………εG ( x )

گراف حاصلضربی…………………………………………………………………………………..G H

گراف ترکیبی………………………………………………………………………………………….G H

گراف الحاقی…………………………………………………………………………………………G H

گراف ستاره…………………………………………………………………………………………………S n

گراف کامل دوبخشی…………………………………………………………………………………K m ,n  

گراف مسیر …………………………………………………………………………………………………Pn

  مجموعه گرافهای تک دور n راسی……………………………………………………………..An

مجموعه گرافهای تک دور n راسی با دوری به U n r, ………………………………………. r

مجموعه همه مسیرها بین πi ,j …………………………………………………………………… i , j

گراف نسر………………………………………………………………………………………. (, )KG m n

گراف فرد……………………………………………………………………………………………………On   

دور با n راس…………………………………………………………………………………………….Cn

گرافهای دو دور………………………………………………………………………………………..Bn  

 خودریختی گراف………………………………………………………………………………… ( )Aut G

جایگشت………………………………………………………………………………………………………σ

انتقال یک راس…………………………………………………………………………………………()T u

شاخص وینر گراف……………………………………………………………………………….W (G )

شاخص سگد گراف………………………………………………………………………………..()Sz G

شاخص سگد اصلاح شده گراف……………………………………………………………( )*Sz G

اختلاف شاخص سگد با وینر……………………………………………………………………η(G )

 فصل اول

تعاریف و مفاهیم اساسی

1 -1 – مقدمه

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

برای نگارش این فصل از منابع [1 6] و 11[] و [16] و 21[] و [23] استفاده شده است.

1 -2 – تعاریف و مفاهیم اساسی

یک گراف عبارت است از G (V (G ),E(G ))، که در آن (       )V G مجموعهای ناتهی و

( )E G مجموعهای از زیرمجموعههای دو عضوی ( )V G است. عناصر ( )V G را رئوس G و عناصر ( )E G را یالهای G مینامیم. تعداد رئوس و یالهای G را به ترتیب مرتبه و اندازهی G نامیده و با ( )V G و ( )E G نشان میدهیم. دو راس که بر روی یال مشترکی واقع باشند، مجاور نامیده میشوند. به همین ترتیب، دو یال واقع بر روی یک راس مشترک نیز مجاورند. یک یال با دو سر یکسان، طوقه نامیده میشود. یک گراف ساده است، اگر هیچ طوقهای نداشته باشد و بین هر دو راس آن، بیش از یک یال نباشد. گراف G را متناهی میگوییم هرگاه E G( ) ,V G( ) . گراف G را یک ( ,n m)گراف گوییم هرگاه V G( ) n و E G( ) m . اگر v یک راس دلخواه از

G باشد. درجه v که با deg(v ) نمایش داده میشود، برابر تعداد راسهایی است که با راس v، مجاورند. درجهی مینیمم راسهای گرافG  را با ((G نشان میدهیم. اگر درجه هر راس گراف G برابر با k باشد، G  را یک گراف k– منتظم گوییم. اگر گراف G به ازای یک عدد صحیح نامنفی k ،k– منتظم باشد، G  را منتظم گوییم. گراف سادهای که در آن هر دو راس متمایز، با یک یال به یکدیگر متصل شده باشند، گراف کامل نامیده میشود. گراف کامل باn  راس را با K n نشان میدهیم.

تعریف 121 گراف دوبخشی، گرافی است که میتوان مجموعهی راسهای آنرا به دو زیرمجموعهی X و Y چنان افراز کرد که یک سر تمام یالهای آن در X و سر دیگر آنها در Y باشد. یک گراف دوبخشی کامل، یک گراف دوبخشی با بخشهای X و Y است که در آن هر راس X، به هر راس Y، وصل شده باشد. اگر X m و Y n ، گراف دوبخشی کامل را با K m ,n نشان میدهیم.

تعریف122 – فرض کنیدG  یک گراف و u و v دو راس از G باشند. یک گشت از u به v یک دنبالهی متناهی و متناوب از راسها و یالهای مجاور مثل u v ev v e v1 1n n1 n1 v که در آنei v vi 1 i ، به ازای  i n1، است.

یک مسیر از u به v گشتی است که شامل یال تکراری نباشد. یک دور ساده، یک مسیر است که نقطه شروع و پایان آن راسی یکسان باشد و هیچ راس دیگر در آن تکراری نباشد. یک دور n راسی را با Cn نشان میدهند. همچنین طول یک مسیر برابر است با تعداد یالهایی که مسیر را به وجود آوردهاند. معمولا برای نمایش یک مسیر n راسی از نماد Pn استفاده میشود.

قضیه 123– گراف G دوبخشی است اگر و فقط اگر شامل دور فرد نباشد.

اثبات. به مرجع 3[] مراجعه شود.

تعریف124 – فرض کنید G گراف همبند با مجموعهی رئوس (     )V G و مجموعهی یالهای

( )E G باشد. برای دو راس دلخواه u,v V فاصله بین u و v که با نماد dG u ,v نشان داده میشود و برای سادگی از d u,v استفاده میکنیم، برابر است با طول کوتاهترین مسیری که u را به v وصل میکند. ماکزیمم فاصله در گراف G، قطر G نامیده میشود و با d یا D نشان داده می- شود.

فاصله یک راس u از یال ( )e  xy E G، برابر با طول کوتاهترین مسیری است که u را به یکی از دو انتهای یال e وصل میکند.

لم 125– گراف G، همبند است اگر و فقط اگر برای هر افراز از راسهای G به دو مجموعه ناتهی، یالی از G با نقاط پایانی در هر یک از دو مجموعه وجود داشته باشد.

اثبات. به مرجع 3[] مراجعه شود.

تعریف 126– یک زیرگراف از G، گرافی مثل H است، بهطوریکه V ( H ) V (G ) و E( H ) E(G ) و برای بیان این مطلب که H زیر گراف G است از نماد H G استفاده میکنیم. یک زیرگراف القایی از G، زیرگرافی مانندH  است به طوریکه هر یال از G که دو انتهایش در V ( H ) باشند یالی از E ( H ) باشد. در صورتیکه زیرگراف H از G در شرط V ( H ) V (G ) صدق کند آنرا یک زیرگراف فراگیر از G مینامیم.

یک گراف که دارای دور نباشد گرافی بیدور است. یک جنگل یک گراف بیدور است و درخت، یک گراف بیدور همبند است. راس آویزان، راسی از درجهی یک است. یک درخت فراگیر، یک زیرگراف فراگیر است که درخت باشد.

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

تعریف 128یک بلوک از گراف G عبارت است از یک زیرگراف همبند ماکسیمال از G که دارای راس برشی نباشد.

اگر G همبند بوده و دارای راس برشی نباشد، آنگاه G خود یک بلوک است.

یک خوشه از گراف G یک زیرگراف کامل ماکسیمال است.

گرافهای بلوکی گرافهایی هستند که هر بلوک آنها یک خوشه است و یک درخت بلوکی گراف G، درختی است که رئوس آن متناظر با بلوکها و رئوس برشی Gمیباشند.یالهایدرخت

بلوکی یک راس برشی را به بلوک B متصل میکنند به طوریکه (v V (B .

مثال129یالها و راسهای برشی گراف G در شکل زیر مشخص شده است.

 

1-1 یالها و راسهای برشی گراف G

تعریف 12°1 مکمل یک گراف سادهی G را با G نشان میدهیم و آن، گرافی است با همان مجموعهی راسهای G، بهطوریکه u و v در G مجاورند اگر و فقط اگر u و v در G مجاور نباشند.

تعریف 1211 یک k رنگآمیزی از G تابعی است مثل f :V (G ) { 12, ,…,k } از مجموعه رئوس به مجموعه رنگهای { 12, ,…,k }. رنگآمیزی فوق را k رنگآمیزی سره مینامیم هرگاه رئوس مجاور دارای رنگهای متفاوت باشند. گراف k ،G رنگپذیر است اگر دارای یک k رنگآمیزی سره باشد. کوچکترین عدد که در آن گراف G، گرافی k رنگپذیر است را عدد رنگی گراف نامیده و با (G ) نشان میدهیم. اگر (G ) k، آنگاه G، گرافی k رنگی است.

تعریف 1213فرض کنید G گرافی همبند و e  uv   E(G )، در اینصورت

N eu ( ) {w V d uw d v w: ( , ) ( , )},   N ev ( ) {w V d v w d uw: ( , ) ( , )},

N e( )  {w V d v w: ( , ) d uw( ,            )}.

همچنین تعداد رئوس N (e)u و ()N ev  و ()N e  را به ترتیب با n (e)u و ()n ev  و ()n e نشان میدهیم.

تعریف 1214 – زیرگراف H از G را ایزومتریک مینامیم هرگاه برای هر زوج نامرتب

.G  H و مینویسیم d x yH (           , ) d x yG (                           ,  ) ،H از رئوس x y, 

یک شاخص توپولوژیکی یک مقدار عددی وابسته به یک گراف است که تحت یکریختی گراف- ها پایدار است.

لم 1215 – گراف G با یک یال e uv را در نظر بگیرید. اگر رئوس x N (e)u                         و

.d u x( , ) d v y( ,   ) مجاور باشند، آنگاه y N v ( )e

اثبات. ( برهان خلف ) فرض کنید (  , )d u x( , ) d v y. بدون کاستن از کلیت مساله، فرض کنید

(  , )d u x( , ) d v y. در اینصورت داریم:

d u y( , )  d u x( , )d x y( , ) d v y( , ) .

چون 1d x y( ,          ) ، از اینرو y N v ( )e و این متناقض با فرض است.                 

نتیجه 1216 – فرض کنید G گرافی ساده از مرتبهی n، دارای t(G ) مثلث باشد. در اینصورت داریم:

v vi         jE G( ) N i N j3t G( )

که N i N j تعداد همسایههای مشترک  vi و v j است. N i  و N j را با توجه به تعریف 1-2-13 در نظر بگیرید.

نتیجه 1217 فرض کنید t(G ) و t(G ) به ترتیب تعداد مثلثهای G و G باشند. در اینصورت اگر دنباله درجات G برابر با 1 ,2dn,…,d d باشد آنگاه داریم:

t G( )t G( ) 21in1 di2  (n 1)m 61 n n( 1)(n 2).

اثبات. به مرجع 5 مراجعه شود.                                                                           تعریف 1218– دو گراف G و H را یکریخت گوییم و با G H نشان میدهیم. هرگاه تابع ( )f :V G( ) V H موجود باشد که در شرط زیر صدق کند:

  xy E G(   )  f ( ) (x f  y )E H(  ).

دو گراف G و H را همیومورف (همسانریخت) مینامیم هرگاه گرافی چون K وجود داشته باشد که با استفاده از آن و احتمالا درج تعدادی رئوس جدید روی یالهای K، بتوان به G و H رسید.

تعریف 1219– گراف G را بدون مثلث گوییم هرگاه شامل زیرگرافی یکریخت با 3K  نباشد.

در واقع، گرافهای بدون مثلث، نمیتوانند شامل زیرگرافی یکریخت با یک K k به ازای 3k  باشند.

تعریف 1220– یک گراف را Θگراف نامیم هرگاه شامل سه مسیر مجزای داخلی متصل به دو راس ثابت باشند.

لم 1221– فرض کنید ( ,G (V E یک Θگراف و ( )e  uv E G. در اینصورت n eu ( )n ev ( )  اگر و فقط اگر e در یک مسیر با طول فرد، در وسط مسیر قرار بگیرد.

اثبات. فرض کنید x و y راسهایی از G با درجه سه باشند و e uv متعلق به i ) P ( )i – امین مسیر بین x و y ) باشد. با توجه به N u ( )e و N v ( )e، سه حالت وجود دارد:

حالت اول. x  و y در مجموعههای متفاوت باشند. ادعا میکنیم:

n eu ( )n ev ( )  b ai  i

به طوریکه ai ( به همین ترتیب bi ) فاصله بین راس x ( به همین ترتیب y ) و یال e میباشد. فرض میکنیم که x N y Nu , v باشد، از اینرو به تعداد a bi i راس در مسیر i ) P ( )i

 


مقطع : کارشناسی ارشد

دانلود بخشی از رابطه بین شاخص سگد و شاخص وینر گراف

قبل از خرید فایل می توانید با پشتبانی سایت مشورت کنید