چکیده 

امروزه نظریه گراف به عنوان یکی از شاخه هاي پرکاربرد ریاضیات و در واقع به عنوان پلی مستحکم میان ریاضیات محض و ریاضیات کاربردي شناخته می شود. به همین منظور دانشمندان و پژوهشگران نظریه گراف در کنار تلاش هایی که براي شناسایی پارامترهاي گوناگون گراف ها صورت می دهند؛ همواره کاربرد این نتایج را در زمینه هاي گوناگون مانند فیزیک و شیمی، نظریه شبکه ها و ارتباطات؛ دنبال می کنند. از جمله موضوعاتی که در چند دهه اخیر توجه ویژه اي را به خود جلب کرده اند می توان به ماتریس لاپلاسین یک گراف و چند جمله اي مشخصه آن و ضرائب و ریشه هاي این چند جمله اي که مقادیر ویژه لاپلاسین نامیده می شوند و به طور خاص به دومین مقدار ویژه کوچک ماتریس لاپلاسین که به همبندي جبري معروف است؛ می توان اشاره کرد. در این نوشتار به بررسی این پارامترها در سه خانواده از گرافها پرداخته شده و برخی نتایج بدست آمده در رابطه با ضرائب چند جمله اي مشخصه لاپلاسین و نیز همبندي جبري، ارائه شده است. 

واژه هاي کلیدي: 

ماتریس لاپلاسین، ضرائب لاپلاسین، چند جمله اي مشخصه، مولفه پرون، ماتریس گلوگاه، گراف هاي بدون دور، گراف هاي تک دوري، گراف هاي دو دوري.

فهرست مطالب

فصل اول:مقدمات و مفاهیم اولیه 

مقدمه …………………………………………………………………………………………………………………………………  2

تعاریف مقدماتی نظریه گراف ………………………………………………………………………………………………  2

ماتریس لاپلاسین یک گراف …………………………………………………………………………………………………  4

فصل دوم:ضرائب لاپلاسین در گراف ها 

مقدمه ……………………………………………………………………………………………………………………………….  10

خانواده گراف هاي بدون دور …………………………………………………………………………………………….  10

تبدیل …………………………………………………ا………………………………………………………………..  11

تبدیلσ …………………………………………………..ا………………………………………………………………..  14

خانواده گراف هاي تک دوري …………………………………………………………………………………………….  16

تبدیل ………………………………………………….ا…………………………………………………………………..  19

تبدیل …………………………………………………….ا…………………………………………………………………  21

گراف هاي دو دوري ……………………………………………………………………………………………………….  25

فصل سوم:همبندي جبري در خانواده هایی از گراف ها 

خانواده درخت ها …………………………………………………………………………………………………………….. 36

پیوند زدن یک یال …………………………………………………………………………………………………………..  38

فرو ریختن یک یال …………………………………………………………………………………………………………..  44

ادامه ي فهرست مطالب

خانواده گراف هاي تک دوري …………………………………………………………………………………………….  50

فصل چهارم:نتایج دیگري در رابطه با همبندي جبري

مقدمه ……………………………………………………………………………………………………………………………… 69

همبندي جبري و گراف هاي ایجاد شده از عملگرها ……………………………………………………………. 69

پیوست ………………………………………………………………………………………………………………………………..  75

فهرست جداول

– جدول شماره 4 -1 رابطه بین ((Gi ),(G که در آن Gi مولفه اي از یک عملگر روي

Gاست.  ………………………………………………………………………………………………………………………………  69

جدول 4 -2 برخی گراف ها با همبندي جبري محاسبه شده …………………………………………………… 70

جدول 4 -3 برخی پارامترهاي موثر بر کران هاي همبندي جبري ……………………………………………..  71

جدول شماره 4 -4 برخی کران هاي همبندي جبري وابسته به سایر پارامترهاي گراف ………………..  73

فهرست شکل ها

شکل شماره (2 -1) تبدیلروي راسw از گرافG   ………………………………………………………….  11

شکل شماره (2 -2) تبدیل σ روي راس u ……………………………………………………………………………  15

شکل شماره (2 -3) تبدیل γ روي راس w ………………………………………………………………………….. 19

شکل شماره (2 -4) …………………………………………………………………………………………………………… 21

شکل شماره (2 -5) تبدیل τ……………………………………………………………………………………………….. 22

شکل شماره (2 -6) گراف (G(a,b,c و گراف (0,G(a c,b ………………………………………………..  24

شکل شماره (2 -7) …………………………………………………………………………………………………………… 26

شکل شماره (2 -8) …………………………………………………………………………………………………………… 26

شکل شماره (2 -9) …………………………………………………………………………………………………………… 27

شکل شماره (2 -10) ………………………………………………………………………………………………………….  29

شکل شماره (2 -11) ………………………………………………………………………………………………………….  32

شکل شماره (3 -1) …………………………………………………………………………………………………………… 39

شکل شماره (3 -2) …………………………………………………………………………………………………………… 44

شکل شماره (3 -3) …………………………………………………………………………………………………………..  47

شکل شماره (3 -4) …………………………………………………………………………………………………………..  48

شکل شماره (3 -5) …………………………………………………………………………………………………………… 50

شکل شماره (3 -6) …………………………………………………………………………………………………………… 51

ادامه ي فهرست شکل ها

شکل شماره(3 -7) ……………………………………………………………………………………………………………..  53

شکل شماره (3 -8) ………………………………………………………………………………………………………………. 65

شکل شماره (3 -9) …………………………………………………………………………………………………………… 66

پیشگفتار: 

در چند دهه اخیر جبر و جبر خطی به کمک نظریه گراف آمده و ابزارهاي مفیدي را براي پژوهش در زمینه هاي گوناگون نظریه گراف فراهم کرده اند. مخصوصا مطالعۀ گراف ها با استفاده از ماتریس هایی که به آن ها نسبت داده می شوند بسیار مورد توجه قرار گرفته است. ماتریس مجاورت و ماتریس لاپلاسین از جمله ماتریس هایی هستند که به گراف نسبت داده می شوند. بررسی این ماتریس ها و به خصوص مقادیر ویژة آن ها نتایج شگفت انگیزي در رابطه با ویژگی هاي ساختاري گراف ها در پی داشته است.

چند جمله اي مشخصۀ ماتریس لاپلاسین علاوه بر این که به لحاظ زمینه اي براي شناسایی پارامترهاي لاپلاسین یک گراف ارزشمند است؛ به لحاظ کاربردي نیز براي شناسایی بهتر گراف هاي مولکولی بسیار مهم است. پژوهش هاي متعددي که درباره این چند جمله اي و کاربردهاي آن در تخمین انرژي هاي مولکولی صورت گرفته مهر تاییدي بر اهمیت این چند جمله اي و ضرائب آن است. ثابت شده است که مقایسۀ انرژي بین گراف هاي مولکولی با مقایسۀ ضرائب چند جمله اي مشخصۀ لاپلاسین آن ها رابطه دارد. به همین منظور یافتن یک ترتیب مناسب براي این ضرائب در خانواده هاي گوناگون گراف ها به یکی از موضوعات مورد علاقه پژوهشگران تبدیل شده است.

مقادیر ویژة ماتریس لاپلاسین نیز در زمینه هاي مختلفی از ریاضیات به ویژه در ریاضیات گسسته و بهینه سازي ترکیباتی کاربرد دارد. اگرچه ماتریس مجاورت و مقادیر ویژه آن بیش تر از ماتریس لاپلاسین مورد بررسی و پژوهش قرار گرفته اند اما بنا به پژوهش هاي صورت گرفته مقادیر ویژه لاپلاسین، شهودي تر و بسیار مهم تر از طیف ماتریس مجاورت هستند.

بین تمام مقادیر ویژة لاپلاسین گراف، یکی از محبوب ترین ها دومین مقدار ویژه کوچک لاپلاسین است که توسط فیدلر، همبندي جبري نامیده شد. اهمیت آن به دلیل این واقعیت است که همبندي جبري پارامتر بسیار مناسبی براي سنجیدن چگونگی همبندي یک گراف است. به عنوان مثال این قضیه وجود دارد که یک گراف همبند است اگر و تنها اگر همبندي جبري آن مخالف صفر باشد.

اخیرا همبندي جبري بیش تر مورد توجه قرار گرفته؛ به طوري که پژوهش هایی  در رابطه با همبندي جبري، پیرامون کاربردهاي آن در مسائل دشوار نظریه گراف مانند تشریح ساختار گراف ها، گراف هاي وزن دار، قدر مطلق همبندي جبري، عدد هم پیرامونی، جنس گراف و همچنین کاربردهاي همبندي جبري در مسائل بهینه سازي ترکیباتی مانند مسئله برش ماکسیمال، مسئله فروشنده دوره گرد و غیره صورت گرفته است. در فصل اول به بیان مقدمات و مفاهیم اولیه پرداخته می شود که انگیزه اي براي ورود به مباحث فصل هاي بعد خواهد بود. در فصل دوم سه خانواده از گراف ها را از نظر مرتب سازي ضرائب لاپلاسین و تعیین بیشترین و کمترین ضرائب لاپلاسین در هر خانواده مورد

مطالعه قرار خواهیم داد. در فصل سوم نیز همان خانواده ها را به لحاظ همبندي جبري بررسی خواهیم کرد و نهایتا در فصل چهارم به بیان اجمالی برخی نتایج بدست آمده درباره همبندي جبري و ارائه کران هاي متنوع براي این پارامتر خواهیم پرداخت.

فصل اول 

مقدمات و مفاهیم اولیه

مقدمه

در این فصل با مفاهیم ابتدایی نظریه گراف، از قبیـل تعریـف گـراف، رأس، یـال، گـراف همبنـد، مسیر، جنگل، درخت و تعاریف اولیه گراف ها آشنا خواهیم شد. سپس با کمک این مفاهیم، مـاتریس لاپلاسین یک گراف و چند جمله اي مشخصه ماتریس لاپلاسین یک گراف را تعریف کرده؛ و بخشی از ویژگی هاي آن را بیان خواهیم کرد.

1.1. تعاریف مقدماتی نظریه گراف

تعریـف : گـراف G یـک مجموعـه نـاتهی و متنـاه ی(V (G از عناصـري بـه نـام رأس؛ و یـک مجموعه (E(G از زیر  مجموعه هاي دو عنصري (V (G است.

به هر یک از اعضاي (E(G یک یال گفته می شود. دقت کنید که ممکن اسـت (E(Gتهـی باشـد . اگـر euv یالی از گرافG باشد، می گوییمu  وv درG  مجاورند؛ یـا یـال e دو رأسu  وv را بـه هـم متصل می کند.

تعریف: تعداد رئوس متصل به رأسv را درجـه رأس v مـی نامنـد و آن  را بـا (deg(v نمـایش می دهند. در این نوشتار گاهی به منظور جلوگیري از پراکندگی و ابهام، براي نمایش رئوس و یال ها از اندیس استفاده شده است. به طور مثال 1v و 2v به ترتیب به معنـی رئـوس شـماره 1 و2 از گـراف مورد نظر هستند. به طریق مشابه 1e و  2eبه ترتیب به معناي یال هاي شماره 1 و 2 می باشند.

تعریف: گرافی که درجه تمام رئوسش برابرr باشد، گراف r -منظم نامیده می شود. 

تعریــف: یــک گشــت در گــر افG ، یــک دنبالــه متنــاوب از رئــوس و یــال هــا بــه فــرم W :v0e1v1e2v2envn اسـت، کـه ابتـدا و انتهـا آن رئـوس هسـتند و بـه ازاي i 1,….,n داریـم:

.ei vi1vi

به منظور رعایت اختصار در دنباله فوق از نوشتن ei ها می توان خودداري کرد.

تعریف: یک دور، یک گشت به فـرم v0v1….vn اسـت بـه طـوري کـه v0 vn؛ و نیـز رئـوس

1v1,v2,…,vn متمایز باشند.

تعریف: یک گشت که رأس تکراري نداشته باشد، یک مسیر نامیده می شود.

تعریف: مسیر P:v1v2vn را یک مسیر آویزان می نامیم. هرگاه 1deg(vn ) و بقیه رئوس بجز احتمالاً 1v از درجه دو باشند. به طور خاص یال euv را یک یال آویزان و یا یک برگ مـی نـامیم، هرگاه 1deg(v) .

تعریف: فاصله دو رأس u و v در گرافG   که آن را با نماد (d(u,v  نمایش می دهیم؛ عبارت است از طول کوتاه ترین مسیر موجود از u بهv. 

تعریف: فرض کنیدv رأسی از گرافG   باشد در این صورت:

  • خروج از مرکز به صورت زیر تعریف می شود:

e(v)  max{d(u,v) | uV (G)}.

  • قطر گراف به صورت زیر تعریف می شود:

diam(G)  max{e(v) | vV (G)}.

تعریف: گرافG  را همبند می گوئیم هرگاه بـه ازاي هـر دو رأس دلخـواه u و v از گـراف G، مسیري بینu  و v موجود باشد. در غیر اینصورت گراف G را ناهمبند می گوئیم.

تعریف: یالeuv  را یک یال برشی می گویند هرگاه با حذف آن، گراف حاصل ناهمبنـد باشـد . بـه طور مشابه رأسv را یک رأس برشی می نامند. هرگاه با حذف آن، گراف حاصل ناهمبند شود.

تعریف: به کمترین تعداد رئوسی که با حذف آن ها، گراف باقیمانده ناهمبند شود؛ همبندي رأسی گراف می گویند و آن را با (v(G نمایش می دهند. به طور مشابه به کمتـرین تعـداد یـال هـایی کـه بـا حذف آنها، گراف ناهمبند می شود؛ همبندي یالی گراف می گویند و آن را با (e(Gنمایش می دهند.

تعریف: هر گراف فاقد دور را یک جنگل می نامند.

تعریف: هر گراف همبند و فاقد دور را یک درخت می نامند.

تعریف: فرض کنیدG یک گراف باشد. زیر گراف فاقد دور از گرافG ، کـه شـامل کلیـه  رئـوس G باشد؛ یک جنگل فراگیر ازG  نامیده می شود. به طور مشابه زیر گراف همبند و فاقد دور از گرافG ، که شامل کلیه رئوسG  باشد؛ درخت فراگیر نامیده می شود.

تعریف: یک زیرتقسیم از گرافG ، گرافی است که با اضافه کردن رئوسی از درجه دو به یال هايG  بدست می آید. زیر تقسیم گرافG  را با (S(G نمایش می دهیم.

2.1. ماتریس لاپلاسین یک گراف

فرض کنید که (G(V , E یک گراف بدون جهت ساده با V n رأس و E m یال باشـد . فـرض کنید رئوسG  به صورت 1vn ,…,v2,v برچسب گذاري شده باشند. ماتریس مجـاورت گـراف G بـه صورت زیر تعریف می شود.

A(G)  aij aaijij  10 vviivvjj EE

ماتریس لاپلاسین گراف Gکه آن را با (L(Gنمایش می دهنـد بـه صـورت (L(G) D(G) A(G تعریف می شود که در آن (D(G یک ماتریس قطري nn است که هر درایـه روي قطـر اصـلی آن برابر با درجه رأس نظیرش در گراف G است. چند جمله اي مشخصه لاپلاسین گرافG  که آن را بـا نماد (p(G, x نمایش می دهیم چند جمل هاي مشخصه ماتریس لاپلاسین گرافG  است.

p(G,x)  det(xIn L(G))  n (1)k ck xnk

k0

هر یک از ضرائب این چند جمله اي را یک ضریب لاپلاسین گراف G می نامند. با بهره گیـري از نتیجه زیر از کلمانز و چلنوکوف[1] می تـوان ضـرائب لاپلاسـین گـراف ck (G)) G) را بـر حسـب ساختار زیر درخت هاي گراف G بیان کرد.

فرض کنید F یک جنگل فراگیر ازG  با مولفه هاي Ti باشد (i k1) تعـداد رئـوس Ti را ni در نظر بگیرید و قرار دهید: (F) k ni .

i1

قضیه 1.1 [1]: ضرائب لاپلایسن (cnk (G از تساوي زیر بدست می آیند:

cnk (G)  (F)

FFk

که در آن Fk مجموعۀ تمام جنگل هاي فراگیرG  است که شامل دقیقاk  مولفه هستند.با استفاده از این قضیه در حالت هاي خاص داریم: 1cn1 n(G) ,c1  2m ,cn  0 ,c0  که در آن ((G تعداد درخت هاي فراگیرG  است. علاوه بر این اگرG  یک درخت باشد ضریب (cn2(G برابر اندیس وینر آن خواهد بود. (اندیس وینر برابر است با حاصل جمع فواصل بین تمامی زو جهاي رئوسG )

cn2 (T) W(T)  d(u,v)

u,vV (G)

ماتریس لاپلاسین یک گراف، یک ماتریس متقارن با مقادیر ویژة نامنفی است. در واقع اگر این مقادیر ویژه را با i n)i1) نمایش دهیم؛ می توانیم آن ها را به صورت زیر مرتب سازي کنیم:

1(G)  2(G)  … n (G) 0

ماتریس لاپلاسین بدون علام تG  که آن را ب ا (Q(G نمایش می دهیم به صورت (Q(G) D(G) A(G تعریف می شود. این ماتریس نیز داراي مقادیر ویژة نامنفی 01  2  …n است.

گاتمن[3و2] اخیرا مفهوم انرژي وقوع یک گراف را براساس مقادیر ویژه ماتریس لاپلاسین بی نشان پایه ریزي کرده است. طبق تعریف، انرژي وقوع یک گراف عبارت است از مجموع مجذورات مقادیر ویژة ماتریس لاپلاسین بی نشان به عبارت دیگر:

IE(G)  n i

i1

به طور مشابه انرژي شبه لاپلاسین گراف براساس مقادیر ویژه ماتریس لاپلاسین گراف تعریف می شود. در واقع:

LEL(G)  n1 i

i1

یکی از نکات قابل توجه درباره این دو انرژي این است که اگر گرافG دو بخشی باشد آن گاه مجموعۀ مقادیر ویژه (طیف) هاي (Q(G و (L(G یکسان خواهند بود و لذا (LEL(G) IE(G.

براساس پژوهش هاي صورت گرفتهLEL قادر است برخی از پارامترهاي دسته هاي بزرگی از گراف هاي مولکولی را برآورد کند. به عنوان مثال عدد اکتان، پارامترAF ، آنتروپی، نقطه جوش، نقطه ذوب و غیره از جمله پارامترهایی هستند که از طریقLEL مورد بررسی قرار گرفته اند.

استوانوویچ[4] در پژوهش هایش رابطه اي بین (LEL(G و ضرائب لاپلاسین ارائه کرد که در جایگاه خود بسیار حائز اهمیت است.

قضیه 2.1[4]: فرض کنیدH,G  دو گرافn راسی باشند. اگر (ck (G) ck (H برا يk 1,2,….,n ؛ آن گاه (LEL(G)  LEL(H. علاوه بر این اگر به ازا يk اي (ck (G)  ck (Hآن گاه (LEL(G)  LEL(H.

بر پایه این قضیه یافتن گراف هایی که در خانواده هاي خود بیشترین (کمترین)LELرا دارند از طریق یافتن گراف هایی که در خانواده خود بیشترین (کمترین) ضرائب لاپلاسین را دارند؛ ممکن می شود.

همچنین بررسی مجموعۀ مقادیر ویژة لاپلاسین (طیف لاپلاسین) گراف ها اطلاعات خوبی از ویژگی هاي آن گراف ها بدست می دهد.

قضیه 3.1 [5]: فرض کنیدG  یک گراف سادهn راسی باشد. ماتریس لاپلاسین گرافG داراي خواص زیر  است:

  • (L(G داراي مقادیر ویژه حقیقی و نامنفی است.
  • کوچک ترین مقدار ویژه صفر است و T(1,…,1,1,1) یک بردار ویژه نظیر این مقدار ویژه است.
  • تکرر صفر به عنوان مقدار ویژة (L(G برابر با تعداد مولفه هاي همبنديG است.
  • 1 n و تساوي برقرار است اگر و تنها اگر متممG ناهمبند باشد.
  • .استvدرجۀ راس dv ؛ که در آنn i  2| E(G) | dv

i1                                                     vV (G)

  • اگرG داراي ماکزیمم درجۀ 0 باشد آن گاه 11    و اگرG  همبند باشد تساوي برقرار است اگر و تنها اگر 1n.

در میان تمام مقادیر ویژه لاپلاسین یک گراف، دومین مقدار ویژة کوچک لاپلاسین (1n) بیش ترین توجه را به خود جلب کرده است با استفاده از قضیه معروف ماتریس – درخت به کمک 1n می توان همبندي یا ناهمبندي گراف را تشخیص داد.

قضیه 4.1[6] : (ماتریس – درخت) 

تعداد درخت هاي فراگیر گرافn راسیG  که با ((G نمایش داده می شود برابر است با:

(G)  1n1(G)…n1(G)

که در آن (i (G و 1n و ….,1i مقادیر ویژه ماتریس لاپلاسین گرافG هستند.

از قضیه ماتریس – درخت این نتیجه حاصل می شود که گرافG همبند است اگر و تنها

اگر 0n1(G) (درواقع 0n1(G) ). از آن جایی که این کمیت ، همبندي گراف را می سنجد لذا فیدلر[7] آن را همبندي جبري گراف نامید.


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

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

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