چکیده 

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

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

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

فهرست مطالب

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

مقدمه …………………………………………………………………………………………………………………………………  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] آن را همبندی جبری گراف نامید.


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

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

250,000RIAL – اضافه‌کردن به سبدخرید

450,000RIAL – اضافه‌کردن به سبدخرید

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