ماتریس مجاورت

از ویکیپدیا، دانشنامه آزاد

در نظریه گراف و علوم کامپیوتر ، یک ماتریس مجاورت یک ماتریس مربع برای نمایش یک محدود نمودار . عناصر ماتریس نشان می دهد که آیا جفت رأس در نمودار مجاور هستند یا نه.

در حالت خاص یک نمودار ساده محدود ، ماتریس همجواری یک ماتریس (0/1) است که صفرها روی مورب آن است. اگر نمودار بدون جهت باشد (یعنی همه لبه های آن دو جهته باشد) ، ماتریس مجاورت متقارن است . رابطه بین نمودار و مقادیر ویژه و بردار ویژه ماتریس مجاورت آن در تئوری نمودار طیفی مورد مطالعه قرار گرفته است .

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

فهرست

تعریف [ ویرایش ]

برای یک گراف ساده با مجموعه رئوس U = {u 1 ، ...، u N }، ماتریس مجاورت یک مربع است n × n با ماتریس به طوری که عنصر آن IJ است زمانی که یک یال از راس وجود دارد ui به راسu j و صفر در صورت عدم وجود لبه. [1] عناصر مورب ماتریس همه صفر هستند ، زیرا لبه های یک راس به سمت خود ( حلقه ها ) در نمودارهای ساده مجاز نیستند. همچنین گاهی اوقات در نظریه نمودار جبری جایگزینی عناصر غیر صفر با متغیرهای جبری مفید است. [2]با ذخیره تعداد لبه های بین دو راس در عنصر ماتریس مربوطه و با اجازه دادن به عناصر مورب غیر صفر ، می توان همین مفهوم را به چند نمودار و نمودارهای حلقه ای گسترش داد . حلقه ها ممکن است یک بار (به عنوان یک لبه) یا دو بار (به عنوان دو رخ لبه راس) شمارش شوند ، به شرطی که یک قرارداد سازگار دنبال شود. نمودارهای غیرمستقیم اغلب از قرارداد دوم برای شمارش حلقه ها دو بار استفاده می کنند ، در حالی که نمودارهای جهت دار به طور معمول از قرارداد قبلی استفاده می کنند.

نمودار دو بخشی [ ویرایش ]

ماتریس مجاورت از یک گراف دو بخشی که دو بخش R وs راس می توان در فرم نوشته

${\ displaystyle A = {\ start {pmatrix} 0_ {r، r} & B \\ B ^ {\ mathsf {T}} & 0_ {s، s} \ end {pmatrix}}،}$

که در آن B یک IS R × بازدید کنندگان ماتریس، و 0 R ، R و 0 بازدید کنندگان ، بازدید کنندگان نشان دهنده R × R و بازدید کنندگان × بازدید کنندگان ماتریس صفر است. در این حالت ، ماتریس کوچکتر B منحصراً نمودار را نشان می دهد و قسمتهای باقی مانده A را می توان به عنوان زائد کنار گذاشت. B را گاهی ماتریس biadjacency می نامند .

بعبارت دیگر، اجازه G = ( U ، V ، E ) یک گراف دو بخشی با قطعات U = { تو 1 ، ...، تو تحقیق }، V = { V 1 ، ...، V بازدید کنندگان } و لبه E . ماتریس biadjacency ماتریس r × s 0-1 B است که در آن b i ، j = 1 فقط و فقط اگر ( u i ، v j ) ∈E .

اگر G چند پاراگراف دو پاراگراف یا نمودار وزنی باشد ، عناصر b i ، j به ترتیب تعداد لبه های بین رئوس یا وزن لبه ( u i ، v j ) در نظر گرفته می شوند.

ماتریس همجواری نمودار دو بخشی کاملاً غیر مدول است . این بدان معنی است که تعیین کننده هر زیرماتریک مربع آن −1 ، 0 یا 1+ است.

تغییرات [ ویرایش ]

( ، ب ، ج ) -adjacency ماتریس از یک نمودار ساده است i ، J = اگر ( i ، J ) لبه، است ب اگر چنین باشد، نیست و ج در قطر. ماتریس مجاورت سیدل است (-1، 1، 0) ماتریس -adjacency. این ماتریس در مطالعه نمودارهای کاملا منظم و دو نمودار استفاده می شود . [3]

ماتریس فاصله دارد در موقعیت ( i ، J ) فاصله بین راس پنجم i و پنجم J . فاصله طول کوتاهترین مسیری است که رئوس رابط متصل می کند. تا زمانی که طول لبه ها به طور واضح ارائه نشوند ، طول یک مسیر تعداد لبه های آن است. ماتریس فاصله شباهت به توان بالای ماتریس مجاورت دارد ، اما به جای اینکه فقط بگوییم دو رئوس متصل هستند یا نه (یعنی ماتریس اتصال که حاوی مقادیر بولی است ) ، فاصله دقیق بین آنها را نشان می دهد.

مثالها [ ویرایش ]

نمودارهای بدون جهت [ ویرایش ]

این کنوانسیون به دنبال در اینجا (برای گرافهای بدون جهت) این است که هر یک از لبه اضافه می کند: از 1 به سلول مناسب در ماتریس، و هر حلقه اضافه می کند 2. [4] این اجازه می دهد تا به درجه ای از یک راس به راحتی با در نظر گرفتن مجموع مقادیر پیدا شده است یا در ردیف یا ستون مربوطه در ماتریس مجاورت.

نمودار دارای برچسب	ماتریس همجواری
	${\ displaystyle {\ start {pmatrix} 2 & 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \ end {pmatrix}}$ مختصات 1–6 هستند.
نمودار نائورو	مختصات 0–23 هستند. زمینه های سفید صفر هستند ، زمینه های رنگی یکی هستند.

نمودارهای هدایت شده [ ویرایش ]

ماتریس مجاورت یک نمودار جهت دار می تواند نامتقارن باشد. می توان ماتریس مجاورت یک نمودار جهت دار را تعریف کرد به گونه ای که

یک عنصر غیر صفر A ij یک لبه از i به j یا نشان می دهد
این نشان دهنده یک لبه از j به i است .

تعریف قبلی معمولاً در تئوری نمودار و تحلیل شبکه های اجتماعی (به عنوان مثال جامعه شناسی ، علوم سیاسی ، اقتصاد ، روانشناسی) استفاده می شود. [5] این مورد اخیر در سایر علوم کاربردی (به عنوان مثال ، سیستم های دینامیکی ، فیزیک ، علوم شبکه) که گاهی اوقات A برای توصیف پویایی خطی در نمودارها استفاده می شود ، بیشتر رایج است. [6]

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

نمودار دارای برچسب	ماتریس همجواری
کارگردان گراف کیلی از S 4	مختصات 0–23 هستند. همانطور که نمودار هدایت می شود ، ماتریس لزوماً متقارن نیست .

نمودارهای بی اهمیت [ ویرایش ]

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

خصوصیات [ ویرایش ]

طیف [ ویرایش ]

ماتریس همجواری یک نمودار ساده بدون جهت متقارن است ، بنابراین یک مجموعه کامل از مقادیر ویژه واقعی و یک بردار ویژه متعامد متعامد دارد. مجموعه مقادیر ویژه یک نمودار طیف نمودار است. [7] معمولاً مشخص کردن مقادیر ویژه با ${\ displaystyle \ lambda _ {1} \ geq \ lambda _ {2} \ geq \ cdots \ geq \ lambda _ {n}.}$

بزرگترین ارزش ویژه $\ lambda _ {1}$ در بالا با حداکثر درجه محدود شده است. این را می توان نتیجه قضیه Perron-Frobenius دانست ، اما می توان آن را به راحتی اثبات کرد. بگذارید v یک بردار ویژه باشد که به آن مرتبط است $\ lambda _ {1}$ وx جزء که در آن V است حداکثر ارزش مطلق است. بدون از دست دادن کلیت ، فرض کنید v x مثبت باشد زیرا در غیر این صورت شما به سادگی بردار ویژه را می گیرید $-v$ ، همچنین به $\ lambda _ {1}$ . سپس

${\ displaystyle \ lambda _ {1} v_ {x} = (Av) _ {x} = \ sum _ {y = 1} ^ {n} A_ {x، y} v_ {y} \ leq \ sum _ { y = 1} ^ {n} A_ {x ، y} v_ {x} = v_ {x} \ deg (x).}$

برای نمودارهای منظم d ، d اولین مقدار ویژه A برای بردار v = (1 ،… ، 1) است (به راحتی می توان مقدار ویژه آن را بررسی کرد و به دلیل حد بالا حداکثر است). تعدد این مقدار ویژه تعداد م ofلفه های متصل G به ویژه است ${\ displaystyle \ lambda _ {1}> \ lambda _ {2}}$ برای نمودارهای متصل می توان نشان داد که برای هر مقدار ویژه $\ lambda _ {i}$ ، این برعکس آن است ${\ displaystyle - \ lambda _ {i} = \ lambda _ {n + 1-i}}$ اگر G یک نمودار دو بخشی باشد نیز یک مقدار ویژه A است . [8] به طور خاص - d یک مقدار ویژه از نمودارهای دو بخشی است.

تفاوت ${\ displaystyle \ lambda _ {1} - \ lambda _ {2}}$ است به نام فاصله طیفی و آن را به مربوط گسترش از G . این نیز مفید است را به شما معرفی شعاع طیفی از $آ$ نشان داده شده توسط ${\ displaystyle \ lambda (G) = \ max _ {\ left | \ lambda _ {i} \ right | <d} | \ lambda _ {i} |}$ . این تعداد محدود است ${\ displaystyle \ lambda (G) \ geq 2 {\ sqrt {d-1}} - o (1)}$ . این محدود در نمودارهای Ramanujan ، که در بسیاری از مناطق کاربرد دارند ، محکم است.

ایزومورفیسم و تغییر ناپذیرها [ ویرایش ]

فرض کنید دو نمودار G 1 و G 2 جهت دار یا غیرمستقیم با ماتریس همجواری A 1 و A 2 آورده شده است. G 1 و G 2 هستند ریخت اگر و تنها اگر وجود داشته باشد وجود دارد ماتریس جایگشت P به طوری که

$PA_ {1} P ^ {- 1} = A_ {2}.$

به طور خاص ، A 1 و A 2 مشابه هستند و بنابراین دارای چند جمله ای حداقل ، چند جمله ای مشخص ، مقادیر ویژه ، تعیین کننده و ردیف هستند . بنابراین اینها می توانند به عنوان تغییر شکل یکسان شکل نمودارها عمل کنند. با این حال ، دو نمودار ممکن است مجموعه ای از مقادیر ویژه یکسان را داشته باشند اما یکدست نباشند. [9] گفته می شود که چنین عملگرهای خطی همسان هستند .

قدرت ماتریس [ ویرایش ]

اگر ماتریس مجاورت گراف جهت و یا غیر مستقیم است G ، سپس ماتریس N (یعنی ماتریس از N نسخه از ) دارای تفسیری جالب توجه است: عنصر ( i ، J ) می دهد تعدادی از (به کارگردانی و یا بدون جهت) پیاده روی به طول N از رأس i به راس J . اگر n کوچکترین عدد صحیح غیر منفی است ، به طوری که برای برخی از i ، j ، عنصر ( i ، j) است) از A n مثبت است ، سپس n فاصله بین راس i و راس j است . این به معنی این، برای مثال، که تعدادی از مثلث در گراف بدون جهت G دقیقا اثری از 3 تقسیم بر 6. ماتریس مجاورت می توان برای تعیین اینکه آیا یا نه نمودار استفاده شده است متصل .

ساختار داده ها [ ویرایش ]

ماتریس مجاورت ممکن است به عنوان یک ساختار داده برای نمایش نمودارها در برنامه های رایانه ای برای دستکاری نمودارها استفاده شود. اصلی ترین ساختار داده جایگزین ، که برای این برنامه نیز استفاده می شود ، لیست همجواری است . [10] [11]

از آنجا که هر ورودی در ماتریس همجواری فقط به یک بیت نیاز دارد ، می تواند به صورت بسیار فشرده نمایش داده شود ، فقط اشغال | V | 2 /8 بایت برای نشان دادن یک نمودار، یا (با استفاده از یک فرمت مثلثی بسته بندی شده و تنها ذخیره سازی قسمت مثلثی پایین تر از ماتریس) حدود | V | 2 /16 بایت برای نشان دادن گراف بدون جهت. اگرچه نمایشی مختصرتر ممکن است ، اما این روش به حد پایین نظری اطلاعات برای حداقل تعداد بیت های مورد نیاز برای نشان دادن همه نمودارهای n -vertex نزدیک می شود. [12] برای ذخیره نمودارها در پرونده های متنی، بیت های کمتری در هر بایت می تواند مورد استفاده قرار گیرد تا اطمینان حاصل شود که همه بایت ها کاراکتر متن هستند ، به عنوان مثال با استفاده از نمایش Base64 . [13] این جمع و جور علاوه بر جلوگیری از اتلاف فضای ، محل مراجعه را تشویق می کند . با این حال ، برای یک نمودار پراکنده بزرگ ، لیست های مجاور به فضای ذخیره سازی کمتری نیاز دارند ، زیرا برای نمایش لبه هایی که وجود ندارند ، هیچ فضایی را تلف نمی کنند . [11] [14]

یک شکل جایگزین از ماتریس همجواری (که به فضای بیشتری نیاز دارد) اعداد موجود در هر عنصر ماتریس را با اشاره گرها به اشیا edge لبه (در صورت وجود لبه ها) یا اشاره گرهای پوچ (در صورت عدم وجود لبه) جایگزین می کند. [14] همچنین می توان وزن لبه ها را مستقیماً در عناصر ماتریس همجواری ذخیره کرد. [11]

علاوه بر مبادلات فضایی ، ساختارهای مختلف داده همچنین عملیات مختلف را تسهیل می کنند. یافتن همه رئوس مجاور یک راس معین در یک لیست مجاورتی به همان سادگی خواندن لیست است و متناسب با تعداد همسایگان زمان می برد. با یک ماتریس مجاورت ، باید یک ردیف کامل اسکن شود ، که متناسب با تعداد رئوس کل نمودار ، زمان بیشتری را می گیرد. از طرف دیگر ، آزمایش اینکه آیا لبه ای بین دو راس داده شده وجود دارد را می توان همزمان با یک ماتریس مجاورت تعیین کرد ، در حالی که نیاز به زمان متناسب با حداقل درجه دو راس با لیست مجاورت دارد. [11] [14]

همچنین به [ ویرایش ] مراجعه کنید

منبع

https://en.wikipedia.org/wiki/Adjacency_matrix

+ نوشته شده در سه شنبه بیست و یکم بهمن ۱۳۹۹ ساعت 17:21 توسط علی رضا نقش نیلچی |

ریاضیات

آموزش ریاضی