چکیده

شاخص وینر گراف 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

 


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

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

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