ریاضیات | بهمن ۱۳۹۹

نمودار کامل دو بخشی

گراف کامل دو بخشی

یک گراف کامل دو بخشی با m = 5 و n = 3
رگه ها
n + m
یال ها
mn
شعاع

قطر

ولادت

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

عدد رنگی
2
شاخص رنگی
حداکثر { M ، n }
طیف

نشانه گذاری

جدول گرافها و پاراMها
در حوزه ریاضی نظریه گراف ، گراف کامل یا دو سو یک نوع دوتایی کامل نوع خاصی از گراف دو بخشی است که در آن هر راس مجموعه اول به هر راس مجموعه دوم متصل می شود. [1] [2]
تئوری گراف خود به طور معمول با کار لئونارد اولر در سال 1736 در هفت پل کونیگسببرگ آغاز می شود . با این حال ، در اوایل سال 1669 ، در ارتباط با نسخه ای از آثار Ramon Llull ، ویرایش شده توسط Athanasius Kircher ، نقاشی هایی از گرافهای کامل از دو قسمت چاپ شده بودند . [3] [4] خود لول سه قرن قبل نقاشی های مشابهی را از گرافهای کامل انجام داده بود. [3]

فهرست1تعریف2مثال ها3خواص4همچنین ببینید5منابع
تعریف [ ویرایش ]
یک گراف دو بخشی کامل ، گرافی است که رئوس آن را می توان به دو زیر مجموعه V 1 و V 2 تقسیم کرد ، به طوری که هیچ یال ای هر دو نقطه انتهایی را در یک زیر مجموعه نداشته باشد ، و هر یال ممکن که بتواند رئوس را در زیر مجموعه های مختلف متصل کند ، بخشی از گراف است. یعنی یک گراف دو بخشی است ( V 1 ، V 2 ، E ) به گونه ای که برای هر دو راس v 1 ∈ V 1 و v 2 ∈ V 2 ، v 1 v 2 یک یال در E است. یک گراف کامل دو بخشی با پارتیشن های اندازه | V 1 | = M و | V 2 | = N ، مشخص است K M، N ؛ [1] [2] هر دو گراف با نماد همان ریخت .
مثالها [ ویرایش ]

ستاره گراف K 1،3 ، K 1،4 ، K 1،5 ، و K 1،6 .

گراف کامل دو بخشی K 4،7 نشان می دهد که مشکل کارخانه آجر سازی توران با 4 مکان ذخیره (لکه های زرد) و 7 کوره (لکه های آبی) به 18 محل عبور (نقاط قرمز) نیاز داردبرای هر k ، K 1 ، k ستاره می نامند . [2] همه گرافهای دوبخشی کامل که درختان ستاره است.گراف K 1،3 پنجه نامیده می شود و برای تعریف گرافهای بدون پنجه استفاده می شود . [5]گراف K 3،3 را گراف سودمندی می نامند . این کاربرد از یک معمای ریاضی استاندارد حاصل می شود که در آن سه ابزار باید هر کدام به سه ساختمان متصل شوند. به دلیل غیرپلانر بودن K 3،3 ، حل بدون عبور غیرممکن است . [6]حداکثر دودور هایی که به عنوان زیرگرافهای گراف یک رابطه یافت می شوند ، مفاهیم نامیده می شوند . هنگامی که یک شبکه با گرفتن ملاقات ها و پیوستن این زیرگراف ها تشکیل می شود ، رابطه دارای یک شبکه مفهومی القایی است . به این نوع تحلیل روابط ، تحلیل مفهوم رسمی گفته می شود .
خصوصیات [ ویرایش ]
مثال K p ، p گرافهای کامل دو بخشی [7]
K 3،3
K 4،4
K 5،5

3 یال رنگی
4 یال رنگی
5 رنگ یال
چند ضلعی های پیچیده منظم شکل 2 {4} p دارای گرافهای کامل و کامل با 2 p راس (قرمز و آبی) و p 2 2 یال هستند. آنها همچنین می توانند به صورت p -edgeings رنگ آمیزی شوند.با توجه به گراف دوبخشی، تست که آیا آن را شامل دوبخشی زیرگراف کامل K من ، من برای یک پاراM من یک IS NP کامل مشکل است. [8]گراف مسطح نمی تواند شامل K 3،3 به عنوان یک جزئی ؛ گراف outerplanar نمی تواند شامل K 3،2 به عنوان یک جزئی (اینها شرایط کافی برای planarity و outerplanarity، اما لازم). برعکس ، هر گراف غیرخطی شامل K 3،3 یا گراف کامل K 5 به عنوان جزئی است. این قضیه واگنر است . [9]هر گراف کامل دو بخشی K n ، n یک گراف مور و یک قفس ( n ، 4) است . [10]گرافهای دوتایی کامل K n ، n و K n ، n +1 حداکثر تعداد یال های ممکن را در بین تمام گرافهای بدون مثلث با تعداد راس های یکسان دارند. این قضیه مانتل است . نتیجه مانتل به تعمیم داده شد ک گراف -partite و گراف است که جلوگیری از بزرگتر دار و دسته به عنوان زیرگرافهای در قضیه توران ، و این دو گراف کامل دوبخشی نمونه هایی از هستند گراف توران ، گراف حدی برای این مشکل کلی تر. [11]کامل گراف دو بخشی K M ، N است راس پوشش تعداد از دقیقه { M ، N } و یال پوشش تعداد از حداکثر { M ، N }.گراف کامل دو قطعه K m ، n دارای حداکثر مجموعه مستقل از اندازه حداکثر { m ، n } است.ماتریس مجاورت یک گراف دوبخشی کامل K M ، N مقادیر عددی √ نانوM ، - √ نانوM و 0؛ با ضرب 1 ، 1 و n + m- 2 به ترتیب. [12]ماتریس لاپلاس از گراف دوبخشی کامل K M ، N مقادیر عددی N + M ، N ، M ، و 0؛ با ضرب 1 ، m -1 ، n -1 و 1 به ترتیب.یک گراف کامل دو طرفه K m ، n دارای درختان پوشا m n -1 n m -1 است . [13]گراف دوبخشی کامل K M ، N است تطابق بیشینه اندازه دقیقه { M ، N }.گراف دوبخشی کامل K N ، N است مناسب N یال رنگ آمیزی مربوط به یک مربع لاتین . [14]هر گراف دو بخشی کامل یک گراف مدولار است : هر سه رأس دارای یک میانه است که متعلق به کوتاهترین مسیرها بین هر جفت رأس است. [15]
همچنین به [ ویرایش ] مراجعه کنیدگراف بدون دودور ، یک کلاس از گرافهای پراکنده است که با اجتناب از زیرنویس های کامل دو بخشی تعریف شده استگراف تاج ، گرافی که با حذف یک تطبیق کامل از یک گراف کامل دو بخشی شکل گرفته استگراف چند بخشی کامل ، تعمیم گرافهای کامل دو بخشی به بیش از دو مجموعه راسحمله دودور سواری
منابع
https://en.wikipedia.org/wiki/Complete_bipartite_graph

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

دو نمودار غیر یکریخت زیر هر دو دارای چند جمله ای مشخصه هستند

از طیف یکسانی برخوردار است.

این به عنوان مثال در این پست قدیمی مورد بحث قرار گرفته است .

با این وجود ، در مثالهای ارائه شده ، طیف نمودارها همیشه مقادیر ویژه تکراری دارند. آیا نمونه هایی وجود دارد که چنین نباشد ، بلکه هر ارزش ویژه منحصر به فرد است؟

در مورد یک مسئله متفاوت اما مرتبط: آیا این درست است که اگر دو نمودار فقط مقادیر ویژه منفرد (ضرب 1) در طیف خود داشته باشند ، بنابراین تشخیص اینکه آیا یکدست نیستند آسان است؟

تئوری نمودار یکسان سازی گراف

دو نمودار زیر هر دو دارای چند جمله ای مشخصه هستند

det(λI-A(G))=λ(λ+1)(λ²-2)(λ³-λ²-5λ+1)

که ریشه تکراری ندارد:

این مسئله اساساً با روش بی رحمانه بررسی همه وجود دارد 77نمودارهای -vertex که با GraphDataدستور Mathematica برگردانده شده اند ، که واقعاً پیدا شده اند2626 جفت های طیفی بدون مقادیر ویژه تکراری

بله ، تعیین اینکه ایزومورف هستند یا نه آسان است به شرطی که طیفی باشند و مقادیر ویژه مشخصی داشته باشند (ضرب 1).

اما نمی توانید مستقیماً بگویید که آنها نامتقارن هستند. همانطور که میشا مثالی زد که دارای مقادیر ویژه متمایز است اما غیر همسان نیستند.

اجازه دهید الف ، بآ،بمجاورت یا لاپاسی دو نمودار است که می خواهید آزمایش کنید. ترکیبات اصیل آنها هستندA = UΣتوتیآ=توΣتوتی و B = VΣVتیب=VΣVتی. مقادیر ویژه آنها را ببینید (ΣΣ یک ماتریس مورب است که مقادیر ویژه را نگه می دارد) یکسان هستند و فرض کنید مقادیر متمایزی دارد. سس یک ماتریس مورب است که شامل می شود 1 پوند∓1 و پپ یک ماتریس تغییر مکان است که در آن هر ستون و ردیف 1 واحد است و بقیه آنها 0 است.

اگر یافتید پپ و سس ماتریس هایی که مطابقت دارند پتو= Vسپتو=Vس بنابراین آنها یکدست هستند ، مگر اینکه اینگونه نباشند.

اگر برخی از مقادیر ویژه در تکرار شود ΣΣ، حتی اگر پیدا کنید پپ و سس ماتریسی که مطابقت دارد پتو= Vسپتو=Vس، هنوز هم نمی توانید بگویید که آنها نامتقارن هستند.

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

ماتریس جایگشت

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

در ریاضیات ، به ویژه در تئوری ماتریس ، ماتریس جایگشت یک ماتریس باینری مربع است که دقیقاً یک ورودی از هر ردیف 1 و هر ستون و 0 در جای دیگر دارد. هر ماتریسی از این دست ، مثلاً P ، نشان دهنده یک جایگزینی از عناصر m است و ، هنگامی که برای ضرب ماتریس دیگری استفاده می شود ، مثلاً A ، منجر به تغییر سطرها (هنگام پیش ضرب ، تشکیل PA ) یا ستون ها (هنگام پس از ضرب ، به شکل AP ) از ماتریس .

فهرست

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

با توجه به یک جایگشت π از متر عناصر،

$\ pi: \ lbrace 1، \ ldots، m \ rbrace \ to \ lbrace 1، \ ldots، m \ rbrace$

به صورت دو خطی توسط

${\ start {pmatrix} 1 & 2 & \ cdots & m \\\ pi (1) & \ pi (2) & \ cdots & \ pi (m) \ end {pmatrix}} ،$

دو روش طبیعی برای ارتباط دادن جایگشت با ماتریس جایگشت وجود دارد. یعنی، با شروع متر × متر ماتریس ، من متر ، یا پس و پیش کردن ستون ها و یا تغییر دادن ردیف، با توجه به π . هر دو روش تعریف ماتریس های جایگشت در ادبیات ظاهر می شود و خصوصیات بیان شده در یک نمایش را می توان به راحتی به نمایش دیگر تبدیل کرد. این مقاله در درجه اول فقط به یکی از این بازنمایی ها می پردازد و مقاله دیگر فقط در مواردی ذکر می شود که تفاوتی وجود داشته باشد.

m × m جایگشت ماتریس P π = ( P IJ ) به دست آمده توسط permuting ستون از ماتریس Mi ، این است که، برای هرI ، P ij= 1 اگر j= π (i ) و P ij = 0 در غیر این صورت، در این مقاله به عنوان نمایش ستون معرفی می شود . [1] از آنجا که ورودی های سطر i همه 0 هستند با این تفاوت که a 1 در ستون π ( i ) ظاهر می شود ، ممکن است بنویسیم

$P _ {\ pi} = {\ start {bmatrix} {\ mathbf e} _ {{\ pi (1)}} \\ {\ mathbf e} _ {{\ pi (2)}} \\\ vdots \\ {\ mathbf e} _ {{\ pi (m)}} \ end {bmatrix}} ،$

جایی که ${\ mathbf e} _ {j}$ ، یک بردار مبنای استاندارد ، بردار ردیفی به طول m را نشان می دهد که 1 در موقعیت j و 0 در هر موقعیت دیگر است. [2]

به عنوان مثال ، ماتریس جایگشت P π مربوط به جایگشت است ${\ displaystyle \ pi = {\ start {pmatrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 4 & 2 & 5 & 3 \ end {pmatrix}}}$ است

$P _ {\ pi} = {\ start {bmatrix} {\ mathbf {e}} _ {{\ pi (1)}} \\ {\ mathbf {e}} _ {{\ pi (2)}} \ \ {\ mathbf {e}} _ {{\ pi (3)}} \\ {\ mathbf {e}} _ {{\ pi (4)}} \\ {\ mathbf {e}} _ {{\ pi (5)}} \ end {bmatrix}} = {\ start {bmatrix} {\ mathbf {e}} _ {{1}} \\ {\ mathbf {e}} _ {{4}} \\ {\ mathbf {e}} _ {{2}} \\ {\ mathbf {e}} _ {{5}} \\ {\ mathbf {e}} _ {{3}} \ end {bmatrix}} = {\ start {bmatrix} 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 \ 0 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 \ end {bmatrix}}$

مشاهده کنید که ستون j ماتریس هویت I 5 اکنون به عنوان ستون π ( j ) هفتم P π ظاهر می شود .

نمایش دیگر که با جایگزینی ردیف های ماتریس هویت I m بدست می آید ، یعنی برای هر j ، p ij = 1 اگر i = π ( j ) و در غیر این صورت p ij = 0 باشد ، به عنوان نمایش ردیف شناخته می شود .

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

نمایش ستون یک ماتریس تغییر در کل این بخش استفاده می شود ، مگر اینکه در موارد دیگری مشخص شده باشد.

ضرب کردن $P _ {{\ pi}}$ بار یک بردار ستون g ردیف های بردار را تغییر می دهد:

$P _ {\ pi} {\ mathbf {g}} = {\ start {bmatrix} {\ mathbf {e}} _ {{\ pi (1)}} \\ {\ mathbf {e}} _ {{\ pi (2)}} \\\ vdots \\ {\ mathbf {e}} _ {{\ pi (n)}} \ end {bmatrix}} {\ start {bmatrix} g_ {1} \\ g_ {2} \\\ vdots \\ g_ {n} \ end {bmatrix}} = {\ start {bmatrix} g _ {{\ pi (1)}} \\ g _ {{\ pi (2)}} \\\ vdots \ \ g _ {{\ pi (n)}} \ end {bmatrix}}.$

استفاده مکرر از این نتیجه نشان می دهد که اگر M یک ماتریس مناسب باشد ، محصول ، ${\ displaystyle P _ {\ pi} M}$ فقط جایگزینی ردیف های M است . با این حال ، با مشاهده آن

${\ displaystyle P _ {\ pi} \ mathbf {e} _ {k} ^ {\ mathsf {T}} = \ mathbf {e} _ {\ pi ^ {- 1} (k)} ^ {\ mathsf {T }}}$

برای هر k نشان می دهد که جایگزینی ردیف ها توسط π -1 داده می شود . ( ${\ displaystyle M ^ {\ mathsf {T}}}$ است ترانهاده ماتریس M .)

همانطور که ماتریس جایگشت ماتریس متعامد است (به عنوان مثال ، ${\ displaystyle P _ {\ pi} P _ {\ pi} ^ {\ mathsf {T}} = I}$ ) ، ماتریس معکوس وجود دارد و می توان آنرا نوشت

${\ displaystyle P _ {\ pi} ^ {- 1} = P _ {\ pi ^ {- 1}} = P _ {\ pi} ^ {\ mathsf {T}}.}$

ضرب یک بردار ردیف h بار $P _ {{\ pi}}$ ستون های بردار را تغییر می دهد:

${\ mathbf {h}} P _ {\ pi} = {\ start {bmatrix} h_ {1} \؛ h_ {2} \؛ \ dots \؛ h_ {n} \ end {bmatrix}} {\ start {bmatrix } {\ mathbf {e}} _ {{\ pi (1)}} \\ {\ mathbf {e}} _ {{\ pi (2)}} \\\ vdots \\ {\ mathbf {e}} _ {{\ pi (n)}} \ end {bmatrix}} = {\ start {bmatrix} h _ {{\ pi ^ {{- 1}} (1)}} \؛ h _ {{\ pi ^ {{ -1}} (2)}} \؛ \ نقطه \؛ h _ {{\ pi ^ {{- 1}} (n)}} \ پایان {bmatrix}}$

باز هم ، استفاده مکرر از این نتیجه نشان می دهد که پس از ضرب یک ماتریس M در ماتریس جایگشت P π ، یعنی MP π ، منجر به جا به جایی ستون های M می شود . همچنین توجه داشته باشید که

${\ displaystyle \ mathbf {e} _ {k} P _ {\ pi} = \ mathbf {e} _ {\ pi (k)}.}$

با توجه به دو تغییر مکان π و σ از عناصر m ، ماتریس های جایگشت مربوطه P π و P σ بر روی بردارهای ستون عمل می کنند با

${\ displaystyle P _ {\ sigma} P _ {\ pi} \، \ mathbf {g} = P _ {\ pi \، \ circ \، \ sigma} \، \ mathbf {g}.}$

همان ماتریس هایی که بر روی بردارهای ردیف عمل می کنند (یعنی بعد از ضرب) مطابق با همان قاعده تشکیل می شوند

${\ displaystyle \ mathbf {h} P _ {\ sigma} P _ {\ pi} = \ mathbf {h} P _ {\ pi \ ، \ circ \ ، \ sigma}.}$

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

${\ displaystyle (\ pi \ ، \ circ \ ، \ sigma) (k) = \ pi \ چپ (\ sigma (k) \ راست).}$

اجازه دهید ${\ displaystyle Q _ {\ pi}}$ ماتریس جایگزینی مربوط به π در نمایش ردیف آن باشد. خصوصیات این نمایش را می توان از ویژگی های نمایش ستون از آن زمان تعیین کرد ${\ displaystyle Q _ {\ pi} = P _ {\ pi} ^ {\ mathsf {T}} = P _ {{\ pi} ^ {- 1}}.}$ به خصوص،

${\ displaystyle Q _ {\ pi} \ mathbf {e} _ {k} ^ {\ mathsf {T}} = P _ {{\ pi} ^ {- 1}} \ mathbf {e} _ {k} ^ {\ mathsf {T}} = \ mathbf {e} _ {(\ pi ^ {- 1}) ^ {- 1} (k)} ^ {\ mathsf {T}} = \ mathbf {e} _ {\ pi ( k)} ^ {\ mathsf {T}}.}$

از این نتیجه است که

${\ displaystyle Q _ {\ sigma} Q _ {\ pi} \، \ mathbf {g} = Q _ {\ sigma \، \ circ \، \ pi} \، \ mathbf {g}.}$

به طور مشابه ،

${\ displaystyle \ mathbf {h} \، Q _ {\ sigma} Q _ {\ pi} = \ mathbf {h} \، Q _ {\ sigma \، \ circ \، \ pi}.}$

گروه ماتریکس [ ویرایش ]

اگر (1) نشان دهنده جایگشت هویت، سپس P (1) است ماتریس .

بگذارید S n نشانگر گروه متقارن یا گروه جایگشت ها در {1،2 ، ... ، n } باشد. از آنجا که n وجود دارد! جایگشت ، n وجود دارد ! ماتریس های جایگشت. توسط فرمول های فوق، N × N ماتریس جایگشت یک شکل گروه تحت عمل ضرب ماتریس با ماتریس هویت به عنوان عنصر هویت .

نقشه S n → A ⊂ GL ( n ، Z 2 ) نمایشی صادقانه است . بنابراین ، | الف | = n ! .

ماتریس تصادفی دو برابر [ ویرایش ]

ماتریس جایگشت خود یک ماتریس تصادفی مضاعف است ، اما در تئوری این ماتریس ها نیز نقش ویژه ای دارد. Birkhoff-فون نویمان قضیه می گوید که هر ماتریس واقعی مضاعف تصادفی است ترکیب محدب از ماتریس جایگشت از همان نظم و ماتریس جایگشت دقیقا نقاط شدید از مجموعه ای از ماتریس مضاعف تصادفی. یعنی پلی پتوپ Birkhoff ، مجموعه ای از ماتریس های تصادفی مضاعف ، بدنه محدب مجموعه ماتریس های جایگشت است. [3]

خصوصیات جبری خطی [ ویرایش ]

اثری از ماتریس جایگشت تعداد است نقطه ثابت از جایگشت. اگر جایگشت دارای نقاط ثابت باشد ، بنابراین می توان آن را به صورت چرخه به صورت π = ( a 1 ) ( a 2 ) ... ( a k ) σ نوشت که در آن σ هیچ نقطه ثابتی وجود ندارد ، سپس e a 1 ، e a 2 ، ...، K هستند بردارهای ویژه ماتریس جایگشت.

برای محاسبه مقادیر ویژه ماتریس جایگشت ${\ displaystyle P _ {\ sigma}}$ ، نوشتن $\ سیگما$ به عنوان یک محصول از چرخه ها ، مثلا ، ${\ displaystyle \ sigma = C_ {1} C_ {2} \ cdots C_ {t}}$ . اجازه دهید طول مربوط به این چرخه ها برابر باشد ${\ displaystyle l_ {1} ، l_ {2} ... l_ {t}}$ ، و اجازه دهید ${\ displaystyle R_ {i} (1 \ leq i \ leq t)}$ مجموعه ای از راه حل های پیچیده باشد ${\ displaystyle x ^ {l_ {i}} = 1}$ . اتحاد همه $R_ {i}$ s مجموعه مقادیر ویژه ماتریس جایگشت مربوطه است. تعدد هندسی هر یک از مقادیر ویژه برابر است با تعداد $R_ {i}$ که حاوی آن است. [4]

از تئوری گروه می دانیم که هر جایگزینی ممکن است به عنوان ضرب جابجایی نوشته شود . بنابراین ، هر فاکتور P ماتریس جایگشت به عنوان ضربی از ماتریس های مقدماتی ردیف ، هر کدام دارای تعیین کننده 1 هستند. بنابراین تعیین کننده ماتریس جایگزینی P فقط امضای جایگشت مربوطه است.

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

تغییر سطرها و ستون ها [ ویرایش ]

هنگامی که یک ماتریس جایگزینی P از سمت چپ با یک ماتریس M ضرب می شود تا PM ایجاد کند ، آن ردیفهای M را تغییر می دهد (در اینجا عناصر بردار ستون) ،
وقتی P از راست با M ضرب می شود تا MP ایجاد کند ، ستون های M (در اینجا عناصر بردار ردیف):

P * (1،2،3،4) T = (4،1،3،2) T

(1،2،3،4) * P = (2،4،3،1)

جابجایی های ردیف ها و ستون ها به عنوان مثال بازتاب (به زیر را ببینید) و جایگشت های حلقوی (به ماتریس جایگشت چرخه ای مراجعه کنید ).

نشان دادنبازتاب

جایگشت ردیف ها [ ویرایش ]

ماتریس جایگشت P π مربوط به جایگشت: $\ pi = {\ start {pmatrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 4 & 2 & 5 & 3 \ end {pmatrix}} ،$ است

با توجه به بردار g ،

$P _ {\ pi} {\ mathbf {g}} = {\ start {bmatrix} {\ mathbf {e}} _ {{\ pi (1)}} \\ {\ mathbf {e}} _ {{\ pi (2)}} \\ {\ mathbf {e}} _ {{\ pi (3)}} \\ {\ mathbf {e}} _ {{\ pi (4)}} \\ {\ mathbf {e }} _ {{\ pi (5)}} \ end {bmatrix}} {\ start {bmatrix} g_ {1} \\ g_ {2} \\ g_ {3} \\ g_ {4} \\ g_ { 5} \ end {bmatrix}} = {\ start {bmatrix} g_ {1} \\ g_ {4} \\ g_ {2} \\ g_ {5} \\ g_ {3} \ end {bmatrix}}.$

توضیح [ ویرایش ]

یک ماتریس جایگشت همیشه در فرم وجود دارد

${\ start {bmatrix} {\ mathbf {e}} _ {{a_ {1}}} \\ {\ mathbf {e}} _ {{a_ {2}}} \\\ vdots \\ {\ mathbf { e}} _ {{a_ {j}}} \\\ end {bmatrix}}$

که در آن E i نشان دهندهi هفتم بردار پایه (به عنوان یک ردیف) برای R j را ، و که در آن

${\ start {bmatrix} 1 & 2 & \ ldots & j \\ a_ {1} & a_ {2} & \ ldots & a_ {j} \ end {bmatrix}}$

است جایگشت شکل ماتریس جایگشت است.

اکنون ، در انجام ضرب ماتریس ، اساساً یک جایگشت نقطه از هر ردیف از ماتریس اول با هر ستون از دوم را تشکیل می دهد. در این نمونه ، ما محصول نقطه هر ردیف از این ماتریس را با بردار عناصری که می خواهیم تغییر دهیم ، تشکیل می دهیم. به عنوان مثال ، v = ( g 0 ، ... ، g 5 ) T ،

e a i · v = g a i

بنابراین ، محصول ماتریس جایگشت با بردار v در بالا ، یک بردار به شکل ( g a 1 ، g a 2 ، ...، g a j ) خواهد بود ، و این پس یک جایگشت v است زیرا ما گفته اند که فرم جایگشتی است

${\ start {pmatrix} 1 & 2 & \ ldots & j \\ a_ {1} & a_ {2} & \ ldots & a_ {j} \ end {pmatrix}}.$

بنابراین ، ماتریس های جایگشت به ترتیب ترتیب عناصر در بردارهای ضرب شده با آنها را تغییر می دهند.

فرمهای محدود [ ویرایش ]

آرایه Costas ، یک ماتریس تغییر مکان که در آن بردارهای جابجایی بین ورودی ها همه مشخص هستند
n-queens puzzle ، یک ماتریس جایگزینی که در آن حداکثر یک ورودی در هر قطر و مورب وجود دارد

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

منبع

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

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

معادله مشخصه و مقادیر ویژه و فضاهای ویژه ماتریس مجاورت یک گراف

ماتریس مجاورت
3	2	1
0	1	0	1
1	0	1	2
0	1	0	3

معادله مشخصه و مقادیر ویژه و فضاهای ویژه ماتریس مجاورت عبارتست از:

λ(λ²-2)=0⇒(λ=0 و λ=√2 وλ=–√2)

ε(0)=〈(-1,0,1)〉

ε(-√2)=〈(1,-√2,1)〉

ε(√2)=〈(1,√2,1)〉

+ نوشته شده در شنبه بیست و پنجم بهمن ۱۳۹۹ ساعت 22:47 توسط علی رضا نقش نیلچی |

مثالی از قطری سازی ماتریس مجاورت

ماتریس مجاورتA
1	1	1	1	0
0	0	0	0	1
0	0	0	0	1
0	0	0	0	1
0	0	0	0	1

مقادیر ویژه عبارت است:2و 0و0و0و2-

طیف گراف :

2,0,0,0,-2

بردارهای ویژه متناظر 0:(0و0و1و1-و0) =x1 و (0و1و0و1-و0) =x2و (1و0و0و1-و0)=x3

بردارهای ویژه متناظر 2-:(1و1و1و1و2-)=x4

بردارهای ویژه متناظر 2:(1و1و1و1و2)=x5

ماتریس D برابر است با:

ماتریس D
0	0	0	0	0
0	0	0	0	0
0	0	0	0	0
0	2-	0	0	0
2	0	0	0	0

ماتریس P
2	2-	0	0	0
1	1	1-	1-	1-
1	1	0	0	1
1	1	0	1	0
1	1	1	0	0

معکوس P'=P
1/4-	1/4-	3/4	1/4-	0
1/4-	3/4	1/4-	1/4-	0
3/4	1/4-	1/4-	1/4-	0
1/8	1/8	1/8	1/8	1/4-
1/8	1/8	1/8	1/8	1/4

A =P'DP

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

گراف پترسن

ماتریس مجاورت گراف پترسن
10	9	8	7	6	5	4	3	2	1	برچسب ها
0	0	0	0	1	0	1	1	0	0	1
0	0	0	1	0	1	1	0	0	0	2
0	0	1	0	0	1	0	0	0	1	3
0	1	0	0	0	0	0	0	1	1	4
1	0	0	0	0	0	0	1	1	0	5
1	0	0	0	1	0	0	0	0	1	6
0	0	1	0	1	0	0	0	1	0	7
0	1	0	1	0	0	0	1	0	0	8
1	0	1	0	0	0	1	0	0	0	9
0	1	0	0	1	1	0	0	0	0	10

دارای چند جمله ای مشخص است $(t-1) ^ {5} (t + 2) ^ {4} (t-3)$

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

گراف پترسن

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

گراف پترسن
نمودار پترسن معمولاً به صورت پنج ضلعی با یک پنج ضلعی در داخل و با پنج پرش کشیده می شود.
به نام	جولیوس پترسن
رگه ها	10
لبه ها	15
شعاع	2
قطر	2
ولادت	5
اتومورفیسم ها	120 (S 5 )
عدد رنگی	3
شاخص رنگی	4
شاخص کروماتیک کسری	3
جنس	1
خواص	مکعب Snark کاملاً منظم از راه دور
جدول نمودارها و پارامترها

در زمینه ریاضی نظریه گراف ،گراف پترسن یک نمودار بدون جهت است که دارای 10 رئوس و 15 لبه است . این یک نمودار کوچک است که به عنوان یک مثال مفید و مثال مثال برای بسیاری از مشکلات در تئوری نمودار عمل می کند. نمودار پترسن به نام جولیوس پترسن نامگذاری شده است ، وی در سال 1898 آن را به عنوان کوچکترین نمودار مکعبی بدون پل و بدون رنگ آمیزی سه لبه ساخت. [1]

گرچه این نمودار عموماً به پیترسن نسبت داده می شود ، اما در واقع اولین بار 12 سال قبل ، در مقاله ای توسط آ ب کمپه ( 1886 ) منتشر شده است. کمپ مشاهده کرد که رئوس آن می تواند نمایانگر ده خط پیکربندی دزارگ باشد ، و لبه های آن جفت خطوطی را نشان می دهد که در یکی از ده نقطه پیکربندی با هم مطابقت ندارند.

دونالد نات اظهار داشت که نمودار پترسن "یک پیکربندی قابل توجه است که به عنوان نمونه ای پیشگویی برای بسیاری از پیش بینی های خوش بینانه در مورد آنچه ممکن است برای نمودارها به طور کلی درست باشد ، عمل می کند. [2]

نمودار پترسن در هندسه گرمسیری نیز ظاهر می شود . مخروط بالای نمودار پیترسن به طور طبیعی با فضای مدول منحنی های استوایی منطقی پنج پر مشخص می شود.

فهرست

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

گراف پترسن به عنوان نمودار $KG_ {5،2}$

گراف پترسن است مکمل از نمودار خط از $K_ {5}$ . همچنین نمودار Kneser است $KG_ {5،2}$ ؛ این بدان معنی است که برای هر زیرمجموعه 2 عنصر از یک مجموعه 5 عنصری یک راس دارد و دو راس توسط یک لبه به هم متصل می شوند در صورتی که فقط زیر مجموعه های 2 عنصر مربوط به یکدیگر جدا نباشند. به عنوان نمودار Kneser از فرم $KG_ {2n-1 ، n-1}$ این یک مثال از نمودار عجیب و غریب است .

از نظر هندسی ، نمودار پترسن گرافی است که توسط رئوس و لبه های hemi-dodecahedron تشکیل شده است ، یعنی یک دوازده ضلعی با نقاط ، خطوط و چهره های مخالف که با هم مشخص شده اند.

جاسازی ها [ ویرایش ]

نمودار پیترسن غیرتطیفی است . هر گراف غیر مسطح است به عنوان افراد زیر سن قانونی یا گراف کامل $K_ {5}$ ، یا نمودار کامل دو بخشی $K_ {3،3}$ ، اما نمودار پترسن هر دو را به عنوان خردسال دارد. $K_ {5}$ جزئی را می توان با انقباض لبه های یک تطبیق کامل ، به عنوان مثال پنج لبه کوتاه در تصویر اول ، ایجاد کرد. $K_ {3،3}$ جزئی را می توان با حذف یک راس (به عنوان مثال راس مرکزی نقاشی 3 متقارن) و انقباض یک لبه به هر همسایه راس حذف شده تشکیل داد.

گراف پترسن دارای شماره عبور 2 و 1 مسطح است .

متداولترین و متقارن ترین نقاشی صفحه نمودار نمودار پترسن ، به عنوان پنج ضلعی درون یک پنج ضلعی ، دارای پنج گذر است. با این حال ، این بهترین نقشه برای به حداقل رساندن گذرگاه ها نیست. نقاشی دیگری وجود دارد (در شکل نشان داده شده است) فقط با دو عبور. از آنجا که غیر پلانی است ، در هر نقاشی حداقل یک گذرگاه دارد و اگر یک لبه عبور از هر نقاشی برداشته شود ، غیر پلان می ماند و عبور دیگری دارد. بنابراین ، شماره عبور آن دقیقاً 2 است. هر لبه در این نقاشی حداکثر یک بار عبور می کند ، بنابراین نمودار Petersen 1 مسطح است . بر روی یک تورس گراف پترسن را می توان بدون عبور از لبه ترسیم کرد. بنابراین دارای جنس 1 جهت پذیر است .

گراف پترسن یک نمودار فاصله واحد است : می توان آن را در صفحه با هر واحد دارای طول واحد رسم کرد.

نمودار پترسن همچنین می تواند (با عبور) در صفحه به گونه ای ترسیم شود که تمام لبه ها دارای طول یکسان باشند. یعنی نمودار واحد فاصله است .

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

تقارن [ ویرایش ]

گراف پترسن کاملا منظم است (با امضای srg (10،3،0،1،1)). همچنین متقارن است ، به این معنی که انتقالی لبه ای و انتقالی راس باشد. با شدت بیشتر ، این حالت 3 قوس-انتقالی است: هر مسیر سه لبه کارگردانی در نمودار پترسن را می توان با تقارن نمودار به هر مسیر دیگر تغییر داد. [3] این تنها یکی از 13 نمودار مکعب با فاصله منظم است . [4]

گروه automorphism از گراف پترسن است گروه متقارن $S_ {5}$ ؛ عمل از $S_ {5}$ در گراف پترسن از ساخت آن به عنوان یک نمودار Kneser پیروی می کند . هر یکسان سازی نمودار نمودار پیترسن با خود که رئوس مجاور را شناسایی نمی کند ، یک شکل گیری است. همانطور که در شکل ها نشان داده شده است ، نقاشی های نمودار پترسن ممکن است تقارن پنج یا سه طرفه را نشان دهند ، اما رسم نمودار پترسن در صفحه به گونه ای امکان پذیر نیست که نقاشی گروه تقارن کامل را نشان دهد نمودار

گراف پترسن با وجود تقارن بالا ، نمودار Cayley نیست . این کوچکترین نمودار راس-انتقالی است که نمودار Cayley نیست. [5]

مسیرها و چرخه های همیلتون [ ویرایش ]

نمودار پیترسن به صورت هایپو-هامیلتونی است: با حذف هر راس ، مانند راس مرکزی در نقاشی ، نمودار باقیمانده همیلتونین است. این نقاشی با تقارن مرتبه 3 نقاشی ارائه شده توسط کمپ (1886) است .

نمودار پترسن مسیری همیلتونی دارد اما چرخه همیلتونی ندارد . این کوچکترین نمودار مکعبی بدون پل است که هیچ چرخه همیلتونی ندارد. این هیپوهامیلتونین است ، به این معنی که اگرچه هیچ چرخه همیلتونی ندارد ، اما حذف هر راس آن را همیلتونین می کند و کوچکترین نمودار هیپوهامیلتون است.

نمودار پترسن به عنوان یک نمودار راس-انتقالی متصل به متن محدود که فاقد چرخه هامیلتونی است ، نمونه متقابل نمونه ای از حدس لواز است ، اما فرمول متعارف حدس ، مسیری همیلتون را می طلبد و توسط نمودار پترسن تأیید می شود.

فقط پنج نمودار راس-انتقالی متصل بدون چرخه همیلتونی شناخته شده است: نمودار کامل K 2 ، نمودار Petersen ، نمودار Coxeter و دو نمودار مشتق شده از گراف پترسن و Coxeter با جایگزینی هر راس با یک مثلث. [6] اگر G یک نمودار 2 متصل ، r- قاعده ای با حداکثر 3 r + 1 رئوس باشد ، G G Hamiltonian یا Gگراف پترسن است. [7]

برای دیدن اینکه نمودار پترسن فاقد چرخه C همیلتونین است ، لبه های برش را قطع کنید که 5 چرخه داخلی را از چرخه خارجی جدا کند. اگر چرخه همیلتون وجود داشته باشد ، باید تعداد زوجی از این لبه ها انتخاب شود. اگر فقط دو مورد از آنها انتخاب شده باشد ، رئوس انتهایی آنها باید در دو 5 دوره مجاور باشند که این امکان وجود ندارد. از این رو 4 نفر از آنها انتخاب می شوند. فرض کنید لبه بالایی برش انتخاب نشده باشد (همه موارد دیگر با تقارن یکسان هستند). از 5 لبه چرخه بیرونی ، دو لبه بالایی باید انتخاب شوند ، دو لبه کناری نباید انتخاب شوند و از این رو لبه پایین باید انتخاب شود. دو لبه بالایی در چرخه داخلی باید انتخاب شوند ، اما این یک چرخه غیرپهنا را کامل می کند ، که نمی تواند بخشی از یک چرخه همیلتون باشد. همچنین می توان ده راس را توصیف کردنمودارهای 3 منظمی که دارای چرخه همیلتونی هستند و با یافتن چرخه ای در هر کدام کوتاه تر از هر چرخه موجود در نمودار پترسن ، نشان می دهد که هیچ یک از آنها نمودار پترسن نیستند. هر نمودار سه راس هامیلتونی ده رأسی شامل یک چرخه ده راسی C به علاوه پنج آکورد است. اگر هر وتر دو راس را در فاصله دو یا سه امتداد C از یکدیگر متصل کند ، نمودار دارای 3 چرخه یا 4 چرخه است و بنابراین نمی تواند گراف پترسن باشد. اگر دو وتر رأس مخالف C را به رئوس با فاصله چهار در امتداد C متصل کنند ، دوباره یک 4 چرخه وجود دارد. تنها مورد باقی مانده نردبان موبیوس استبا اتصال هر جفت رأس مخالف توسط یک آکورد ، که دوباره دارای یک 4 چرخه است ، تشکیل شده است. از آنجا که نمودار پترسن دارای محدوده پنج است ، نمی توان از این طریق شکل گرفت و چرخه همیلتونی ندارد.

رنگ آمیزی [ ویرایش ]

4 رنگ از لبه های گراف پترسن

3 رنگ آمیزی رئوس گراف پترسن

نمودار پترسن دارای شماره رنگی 3 است ، به این معنی که رئوس آن می تواند با سه رنگ - اما نه با دو رنگ - رنگی باشد ، به طوری که هیچ لبه ای رئوس همان رنگ را به هم متصل نمی کند. این یک لیست رنگ آمیزی با 3 رنگ ، توسط قضیه بروکس برای رنگ آمیزی لیست دارد.

گراف پترسن دارای شاخص کروماتیک 4 است. رنگ آمیزی لبه ها به چهار رنگ نیاز دارد. به عنوان یک گراف مکعب bridgeless متصل با شاخص رنگی چهار، گراف پترسن است گزارش روز . این کوچکترین مارماهی ممکن است و از سال 1898 تا سال 1946 تنها شناخته شده بود. قضیه snark ، نتیجه ای که توسط WT Tutte حدس زد و در سال 2001 توسط رابرتسون ، سندرز ، سیمور و توماس اعلام شد [8] بیان می کند که هر snark دارای نمودار پترسن به عنوان یک خردسال .

علاوه بر این ، نمودار دارای شاخص کروماتیک کسری 3 است ، اثبات می کند که اختلاف بین شاخص رنگی و شاخص رنگی کسری می تواند به اندازه 1 باشد. حدس طولانی مدت گلدبرگ-سیمور پیشنهاد می کند که این بزرگترین شکاف ممکن است.

Thue به تعداد (یک نوع شاخص رنگی) از گراف پترسن 5 است.

گراف پترسن به حداقل سه رنگ در هر رنگ آمیزی (احتمالاً نامناسب) نیاز دارد که تمام تقارن های آن را بشکند. یعنی عدد متمایز آن سه است. به جز نمودارهای کامل ، این تنها نمودار Kneser است که شماره تمایز آن دو نیست. [9]

خواص دیگر [ ویرایش ]

نمودار پترسن:

3 متصل است و از این رو 3 لبه متصل و بدون پل است. واژه نامه را ببینید .
دارای شماره استقلال 4 و 3 بخشی است. واژه نامه را ببینید .
است مکعب است، تعداد سلطه 3، و دارای یک تطابق کامل و یک 2-عامل .
دارای 6 مسابقه کاملاً مشخص است.
کوچکترین نمودار مکعبی از دور 5 است . (این منحصر به فرد است $(3،5)$ - قفس . در حقیقت ، از آنجا که فقط 10 راس دارد ، منحصر به فرد است $(3،5)$ - نمودار مور .) [10]
کوچکترین نمودار مکعبی با نمودار کالین دو وردیر است که μ = 5 ثابت است . [11]
کوچکترین نمودار پلیس شماره 3 است. [12]
است شعاع 2 و قطر 2. این بزرگترین نمودار مکعب با قطر 2. است [13]
دارای طیف نمودار −2 ، −2 ، −2 ، −2 ، 1 ، 1 ، 1 ، 1 ، 1 ، 3 است.
دارای 2000 درخت پوشا است که بیشترین مقدار از نمودار مکعب 10 راس است. [14]
دارای چند جمله ای رنگی است ${\ displaystyle t (t-1) (t-2) \ چپ (t ^ {7} -12t ^ {6} + 67t ^ {5} -230t ^ {4} + 529t ^ {3} -814t ^ { 2} + 775t-352 \ راست)}$ . [15]
دارای چند جمله ای مشخص است $(t-1) ^ {5} (t + 2) ^ {4} (t-3)$ ، آن را به یک نمودار انتگرال تبدیل می کند - گرافی که طیف آن کاملاً از اعداد صحیح تشکیل شده است.

حدس رنگ آمیزی پیترسن [ ویرایش ]

با توجه به DeVos ، Nesetril و Raspaud ، یک چرخه از نمودار G یک مجموعه است ${\ displaystyle C \ subseteq E (G)}$ به طوری که هر راس نمودار ( V ( G )، C ) حتی درجه دارد. اگر G ، H نمودار باشد ، ما یک نقشه را تعریف می کنیم $\ phi: E (G) \ به E (H)$ در صورت چرخه پیوسته اگر پیش از هر چرخه H چرخه G باشد. یک حدس جذاب از جاگر ادعا می کند که هر نمودار بدون پل دارای یک نقشه مداوم با چرخه به نمودار پترسن است. جائگر نشان داد که این حدس ، حدس 5 دور دوبرابر و حدس برگ-فولکرسون را در بردارد. " [16]

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

خانواده پترسن .

تعمیم گراف پترسنG ( N ، K ) توسط اتصال رئوس تشکیل منظم N -gon به رئوس متناظر یک چند ضلعی ستاره با نماد Schläfli { N / K }. [17] به عنوان مثال ، در این علامت گذاری ، نمودار پترسن G (5،2) است: می توان آن را با اتصال رئوس متناظر یک پنج ضلعی و پنج نقطه ای ایجاد کرد ، و لبه های ستاره هر راس دوم را بهم متصل می کنند. نمودارهای پیترسن تعمیم یافته نیز شامل n- منشور G ( n ، 1) the استنمودار دورر G (6،2) ، نمودار Möbius-Kantor G (8،3) ، دوازده ساله G (10،2) ، نمودار Desargues نمودار G (10،3) و نمودار Nauru G (12،5).

خانواده پترسون شامل هفت نمودار است که می توان از گراف پترسن بر صفر یا چند برنامه از تشکیل Δ-Y یا Y-Δ تبدیل . گراف کامل K 6 نیز در خانواده پترسن. این نمودارها افراد خردسال ممنوعه را برای نمودارهای قابل جاسازی بدون لینک تشکیل می دهند ، نمودارهایی که می توانند در فضای سه بعدی تعبیه شوند به گونه ای که هیچ دو چرخه در نمودار به هم پیوند نخورند . [18]

نمودار Clebsch به شامل تعداد زیادی کپی از گراف پترسن به عنوان زیرگرافهای ناشی از : برای هر رأس V از نمودار Clebsch به، ده غیر همسایگان از V القاء یک کپی از گراف پترسن.

منبع

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

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

نتیجه تصویری برای Eigenvectors of Graphs ones

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

مثال از چند جمله ای مشخصه یک گراف

نتیجه تصویری برای Eigenvectors of Graphs ones

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

نمودار بسیار نامنظم

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

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

فهرست

تاریخچه [ ویرایش ]

نمودارهای نامنظم در ابتدا توسط یوسف علوی ، گری چارتراند ، فن چونگ ، پل اردوس ، رونالد گراهام و اورتود اولرمن مشخص می شدند . [1] انگیزه آنها این بود که "عکس" گراف منظم را تعریف کنند ، مفهومی که کاملاً مورد مطالعه و درک قرار گرفته است.

مکان و نظم [ ویرایش ]

تعریف "نمودار نامنظم" بلافاصله آشکار نبود. در یک نمودار- k منظم ، همه رئوس درجه k دارند . در هر نمودار G با بیش از یک راس ، دو راس در G باید یک درجه داشته باشند ، بنابراین یک نمودار نامنظم را نمی توان به عنوان یک نمودار با تمام رئوس درجات مختلف تعریف کرد. ممکن است وسوسه شود که یک نمودار نامنظم را تعریف کنیم که دارای همه رئوس درجات مشخص است به جز دو ، اما این نوع نمودارها نیز به خوبی درک شده اند و بنابراین جالب نیستند. [2]

بنابراین نظریه پردازان گراف به مسئله نظم محلی روی آوردند. نمودار به صورت محلی در راس به طور منظم است V اگر همه رئوس مجاور به V دارای درجه R . نمودار نتیجه به صورت محلی نامنظم اگر برای هر رأس V از G همسایگان V درجه متمایز، و این نمودار به این ترتیب نمودار بسیار نامنظم نامیده می شوند. [1]

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

برخی از حقایق در مورد نمودارهای بسیار نامنظم که توسط علوی و همکاران شرح داده شده است. : [3]

اگر v یک راس حداکثر درجه d در یک نمودار بسیار نامنظم H باشد ، پس v دقیقاً مجاور یک راس درجه 1 ، 2 ، ... ، d است . [3]
بیشترین درجه در نمودار بسیار نامنظم حداکثر نیمی از راس است. [3]
اگر H یک نمودار بسیار نامنظم با حداکثر درجه d باشد ، می توان با گرفتن دو نسخه از H و افزودن لبه بین دو راس درجه d یک نمودار بسیار نامنظم از درجه d + 1 ساخت . [3]
H ( n ) / G ( n ) به 0 می رود زیرا n به سرعت به بی نهایت می رود ، جایی که H ( n ) تعداد نمودارهای (غیر ایزومورف) بسیار نامنظم با n راس است و G ( n ) تعداد کل از نمودارها با n راس. [3]
برای هر نمودار G ، یک نمودار بسیار نامنظم H وجود دارد که حاوی G به عنوان یک زیرگراف القا شده است . [3]

این آخرین مشاهده را می توان با نتیجه Dénes Kőnig ، که می گوید اگر H یک نمودار با بیشترین درجه r باشد ، در نظر گرفت ، یک نمودار G وجود دارد که r- منظم است و حاوی H به عنوان یک زیرگراف القا شده است. [3]

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

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

منبع

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

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

قفس (تئوری گراف)

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

Tutte (3،8) -cage .

در ریاضی منطقه از نظریه گراف ، یک قفس است گراف به طور منظم که به عنوان چند است راس که ممکن است برای آن دور .

به طور رسمی ، نمودار ( r ، g ) به شکلی تعریف می شود که در آن هر راس دقیقاً r همسایه داشته باشد و کوتاه ترین چرخه طول آن دقیقاً g باشد. مشخص شده است که یک ( R ، G ) -گراف برای هر ترکیبی از وجود دارد R ≥ 2 وG≥ 3. ( R ، G ) -cage یک IS ( R ، G ) -گراف با کمترین تعداد ممکن از رئوس، در میان همه ( r ، g ) - گرافها.

اگر گراف مور با درجه r و اندازه g وجود داشته باشد ، باید یک قفس باشد. علاوه بر این ، محدوده اندازه های نمودارهای مور به قفس تعمیم می یابد: هر قفس با محکم بودن g g باید حداقل

$1 + r \ sum _ {{i = 0}} ^ {{(g-3) / 2}} (r-1) ^ {i}$

رأس ، و هر قفس با حتی مساحت g باید حداقل داشته باشد

$2 \ sum _ {{i = 0}} ^ {{(g-2) / 2}} (r-1) ^ {i}$

رگه ها. هر نمودار ( r ، g ) دقیقاً با این تعداد رئوس با تعریف یک گراف مور است و بنابراین به طور خودکار یک قفس است.

برای ترکیب مشخص r و g ممکن است چندین قفس وجود داشته باشد . به عنوان مثال سه قفس غیر هم شکل (3،10) وجود دارد که هر کدام 70 راس دارند: قفس 10 Balaban ، نمودار Harries و نمودار Harries – Wong . اما فقط یک قفس ( 3،11) وجود دارد: قفس Balaban 11 (با 112 راس).

فهرست

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

درجه یک گراف است چرخه، و یک متصل درجه دو گراف دور به تعداد آن از راس برابر است، بنابراین قفس تنها از علاقه برای می R ≥ 3. ( R ، 3) -cage است گراف کامل K R 1 + در r +1 رئوس ، و ( r ، 4) -cage یک نمودار دوتایی کامل K r ، r روی رئوس 2 r است .

قفس های دیگر قابل توجه عبارتند از:

(3،5) قفس: گراف پترسن ، 10 رئوس
(3،6) - قفس: نمودار هیود ، 14 رئوس
(3،8) قفس: گراف تات -کاکستر ، 30 رئوس
(3،10) - قفس : بلابان 10-قفس ، 70 رئوس
(3،11) - قفس : بلابان 11-قفس ، 112 رئوس
(4،5) قفس: نمودار رابرتسون ، 19 رئوس
(7،5) قفس: نمودار هافمن-سینگلتون ، 50 رئوس.
وقتی r - 1 یک قدرت اصلی است ، قفسهای ( r ، 6) نمودارهای بروز فضاهای تصویری هستند .
وقتی r - 1 یک قدرت اصلی است ، قفس های ( r ، 8) و ( r ، 12) چند ضلعی های تعمیم یافته هستند .

تعداد رئوس در قفسهای شناخته شده ( r ، g ) ، برای مقادیر r > 2 و g > 2 ، غیر از صفحات تصویری و چند ضلعی های تعمیم یافته ، عبارتند از:

g ر	3	4	5	6	7	8	9	10	11	12
3	4	6	10	14	24	30	58	70	112	126
4	5	8	19	26	67	80				728
5	6	10	30	42		170				2730
6	7	12	40	62		312				7812
7	8	14	50	90

علائم تجزیه ای [ ویرایش ]

برای مقادیر بزرگ g ، محدوده مور نشان می دهد که تعداد n رئوس باید حداقل به صورت نمایی به عنوان تابعی از g رشد کند . بدین ترتیب در گرم می توان در بسیاری متناسب با لگاریتم از N . دقیق تر،

$g \ leq 2 \ log _ {{r-1}} n + O (1).$

اعتقاد بر این است که این بند محکم یا نزدیک به محکم است ( Bollobás & Szemerédi 2002 ). بهترین مرزهای شناخته شده پایین در g نیز لگاریتمی است ، اما با یک فاکتور ثابت کوچکتر (به این معنی است که n به صورت نمایی رشد می کند اما با سرعتی بالاتر از حد مور). به طور خاص ، ساخت نمودار Ramanujan تعریف شده توسط Lubotzky ، Phillips & Sarnak (1988) محدودیت

$g \ geq {\ frac {4} {3}} \ log _ {{r-1}} n + O (1).$

این محدودیت توسط Lazebnik ، Ustimenko & Woldar (1995) کمی بهبود یافت .

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

منبع

https://en.wikipedia.org/wiki/Cage_(graph_theory)

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

نمودار منظم

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

تصادفی R به طور منظم نمودار است نمودار انتخاب شده از ${\ displaystyle {\ mathcal {G}} _ {n، r}}$ ، که فضای احتمالی تمام نمودارهای r- منظم را بر روی n رئوس ، که 3 ≤ r < n و nr یکنواخت است ، نشان می دهد. [1] بنابراین این یک نوع خاص از نمودار تصادفی است ، اما محدودیت نظم به طور قابل توجهی ویژگی های نگهداری شده را تغییر می دهد ، زیرا بیشتر نمودارها منظم نیستند.

خصوصیات نمودارهای منظم تصادفی [ ویرایش ]

همانطور که در نمودارهای تصادفی عمومی تر وجود دارد ، می توان ثابت کرد که خصوصیات خاصی از نمودارهای R با قاعده تصادفی تقریباً به طور مجانبی وجود دارد . به ویژه ، برای ${\ displaystyle r \ geq 3}$ ، یک نمودار R- قاعده ای تصادفی از اندازه بزرگ به طور مجانبی تقریباً به طور قطع r- متصل است . [2] به عبارت دیگر ، اگرچه نمودارهای r منظم با قابلیت اتصال کمتر از r وجود دارد ، اما با انتخاب n ، احتمال انتخاب چنین گرافی به 0 می رسد .

اگر $\ اپسیلون$ > 0 یک ثابت مثبت است و d کمترین مقدار را دارد

${\ displaystyle (r-1) ^ {d-1} \ geq (2+ \ epsilon) rn \ ln n}$

پس از آن، به طور مجانبی مطمئنا، تصادفی R نمودار به طور منظم است قطر در اکثر د . همچنین یک مرز پایین تر (پیچیده تر) روی قطر نمودارهای R- منظم وجود دارد ، به طوری که تقریباً تمام نمودارهای r- منظم (از همان اندازه) تقریباً قطر یکسانی دارند. [3]

توزیع تعداد چرخه های کوتاه نیز شناخته شده است: برای ثابت m ≥ 3 ، اجازه دهید Y 3 ، Y 4 ،… ، Y m تعداد چرخه های طول تا m باشد. سپس Y من متغیرهای تصادفی پواسون به صورت مجانبی و با میانگین [4] هستند

${\ displaystyle \ lambda _ {i} = {\ frac {(r-1) ^ {i}} {2i}}}$

الگوریتم نمودارهای تصادفی منظم [ ویرایش ]

اجرای تصادفی نمودارهای r- منظم به طور کارآمد و به روشی بی طرفانه غیرمعمول نیست ، زیرا بیشتر نمودارها منظم نیستند. مدل جفت شدن (همچنین مدل پیکربندی ) یک روش است که طول می کشد است NR امتیاز، و پارتیشن آنها را به N سطل با R امتیاز در هر یک از آنها. گرفتن یک تطبیق تصادفی از نقاط nr ، و سپس انقباض نقاط r در هر سطل به یک راس واحد ، یک نمودار یا چند نمودار منظم r را بدست می آورد . اگر این جسم چندین لبه یا حلقه نداشته باشد (یعنی نمودار است) ، نتیجه لازم است. در غیر این صورت ، راه اندازی مجدد مورد نیاز است.[5]

اصلاح این روش توسط Brendan McKay و Nicholas Wormald ساخته شد. [6]

منبع

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

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

گراف مور

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

در نظریه گراف ، یک گراف مور است نمودار به طور منظم از درجه D و قطر K که تعداد رئوس برابر کران بالا

$1 + d \ sum _ {{i = 0}} ^ {{k-1}} (d-1) ^ {i}.$

یک تعریف معادل از نمودار مور این است که نمودار نمودار باشد $ک$ با دور شدن $2k + 1$ . تعریف معادل دیگری از نمودار مور $G$ این است که آن را محکم است ${\ displaystyle g = 2k + 1}$ و دقیقاً ${\ frac {n} {g}} (m-n + 1)$ چرخه های طول $g$ ، جایی که $n$ و $متر$ به ترتیب تعداد رئوس و لبه های $G$ . در واقع با توجه به تعداد چرخه هایی که طول آنها گراف است ، افراطی هستند. [1]

نمودار مور توسط نام برده شد هافمن و سینگلتون (1960) بعد از ادوارد اف مور ، که این سوال را از توصیف و طبقه بندی این نمودار را مطرح کرد.

نمودارهای مور علاوه بر داشتن حداکثر تعداد راس ممکن برای یک ترکیب معین از درجه و قطر ، دارای حداقل تعداد راس ممکن برای یک نمودار منظم با درجه و دور مشخص شده هستند. یعنی هر نمودار مور یک قفس است . [2] فرمول تعداد رأس در نمودار مور را می توان تعمیم داد تا بتوان تعریفی از نمودارهای مور با یکدست و همچنین دور فرد را ارائه داد و دوباره این نمودارها قفس هستند.

فهرست

رئوس محدود بر اساس درجه و قطر [ ویرایش ]

پترسن گراف به عنوان یک گراف مور. هر درخت جستجو برای اولین بار دارای d ( d -1) i رأس در سطح I است.

بگذارید G هر نمودار با حداکثر درجه d و قطر k باشد ، و درختی را که با جستجو در وسعت تشکیل شده است در نظر بگیرید که از هر راس v شروع می شود . این درخت دارای 1 راس در سطح 0 ( خود v ) و حداکثر d رئوس در سطح 1 (همسایگان v ) است. در سطح بعدی ، حداکثر رئوس d ( d -1) وجود دارد: هر همسایه v از یکی از مجاورتهای خود برای اتصال به v استفاده می کند و بنابراین می تواند حداکثر d -1 همسایه در سطح 2 داشته باشد. به طور کلی ، یک استدلال مشابه نشان می دهد که در هر سطح 1 ≤ من ≤K ، وجود دارد می توانید حداکثر باشد د ( د -1) من راس. بنابراین ، تعداد کل رئوس می تواند حداکثر باشد

$1 + d \ sum _ {{i = 0}} ^ {{k-1}} (d-1) ^ {i}.$

هافمن و سینگلتون (1960) در ابتدا نمودار مور را به عنوان گرافی تعریف كردند كه این محدوده به تعداد رئوس دقیقاً برای آن برآورده می شود. بنابراین ، هر نمودار مور دارای حداکثر رأس های ممکن در میان تمام نمودارها با حداکثر درجه d و قطر k است .

بعداً ، سینگلتون (1968) نشان داد كه نمودارهای مور را می توان به طور معادل با قطر k و اندازه 2k + 1 تعریف كرد . این دو مورد نیاز ترکیب را به زور از نمودار به د به طور منظم برای برخی از د و برای برآوردن به فرمول راس شمارش.

نمودارهای مور به عنوان قفس [ ویرایش ]

به جای اینکه از نظر حداکثر درجه و قطر آن ، تعداد راس های یک نمودار محدود شود ، می توانیم از طریق روش های مشابه ، یک حد پایین تر از تعداد رئوس از نظر حداقل درجه و دور آن محاسبه کنیم . [2] فرض کنید G دارای حداقل مدرک د و دور 2 K 1. خودسرانه یک راس ابتدایی v را انتخاب کنید ، و مانند قبل درخت جستجوی گسترده ای را که در v ریشه دارد ، در نظر بگیرید. این درخت باید یک راس در سطح 0 داشته باشد ( v خودش) و حداقل d رئوس در سطح 1 باشد. در سطح 2 (برای k > 1) ، حداقل باید d ( d باشد)-1) رئوس ، زیرا هر راس در سطح 1 حداقل d -1 مجاورت باقیمانده برای پر کردن دارد ، و هیچ دو راس در سطح 1 نمی تواند مجاور یکدیگر باشد یا یک راس مشترک در سطح 2 باشد زیرا این یک چرخه کوتاه تر ایجاد می کند از حد فرض به طور کلی ، یک استدلال مشابه نشان می دهد که در هر سطح 1 ≤ i ≤ k ، باید حداقل d ( d -1) i رئوس وجود داشته باشد. بنابراین ، تعداد کل رئوس باید حداقل باشد

$1 + d \ sum _ {{i = 0}} ^ {{k-1}} (d-1) ^ {i}.$

در نمودار مور ، این محدوده به تعداد رئوس دقیقاً برآورده می شود. هر نمودار مور دور دقیقا 2 K 1: آن رئوس به اندازه کافی نیست که به دور بالاتر و چرخه های کوتاه تر باعث می شود بیش از حد چند راس در اول وجود دارد ک سطح برخی از اولین درخت جستجوی سطح. بنابراین ، هر نمودار مور دارای حداقل رئوس ممکن در میان تمام نمودارهای دارای حداقل درجه d و قطر k است : این یک قفس است .

حتی برای مسافت 2 کیلو، می توان به طور مشابه یک درخت جستجو در اولین عرض از نقطه میانی یک لبه ایجاد کرد. در نتیجه در حداقل تعداد رئوس در یک نمودار از این دور که با حداقل درجه D است

$2 \ sum _ {{i = 0}} ^ {{k-1}} (d-1) ^ {i} = 1 + (d-1) ^ {{k-1}} + d \ sum _ { {i = 0}} ^ {{k-2}} (d-1) ^ {i}.$

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

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

در قضیه هافمن - سینگلتون بیان شده است كه هر نمودار مور با گوزن 5 باید دارای درجه 2 ، 3 ، 7 یا 57 باشد. نمودارهای مور عبارتند از: [3]

گرافهای کامل $K_ {n}$ در n> 2 گره (قطر 1 ، گوزن 3 ، درجه n-1 ، سفارش n)
چرخه های عجیب و غریب $C _ {{2n + 1}}$ (قطر n ، محفظه 2n + 1 ، درجه 2 ، سفارش 2n + 1)
گراف پترسن (قطر 2، دور 5، درجه 3، سفارش 10)
نمودار هافمن - سینگلتون (قطر 2 ، دور 5 ، درجه 7 ، سفارش 50)
یک نمودار فرضی با قطر 2 ، گوزن 5 ، درجه 57 و نظم 3250 ، که وجود آن ناشناخته است [4]

اگرچه تمام نمودارهای شناخته شده مور نمودارهای انتقالی-راس هستند ، اما ناشناخته (در صورت وجود) نمی تواند راس-انتقالی باشد ، زیرا گروه اتومورفیسم آن می تواند حداکثر 375 نظم داشته باشد ، کمتر از تعداد رئوس آن. [5]

اگر از تعریف کلی نمودارهای مور استفاده شود که نمودارهای مساحت را نیز امکان پذیر می سازد ، نمودارهای مور یکنواخت مربوط به نمودارهای بروز چند ضلعی های تعمیم یافته (احتمالی) است . برخی از نمونه ها چرخه های زوج هستند $C _ {{2n}}$ ، نمودارهای کامل $K _ {{n ، n}}$ با محوطه چهار ، نمودار Heoodood با درجه 3 و اندازه 6 و نمودار Tutte-Coxeter با درجه 3 و محدوده 8. به طور کلی ، شناخته شده است که ، به غیر از نمودارهای ذکر شده در بالا ، تمام نمودارهای مور باید دارای محدوده 5 باشند ، 6 ، 8 یا 12. [6] قضیه زوج همسان نیز از قضیه Feit-Higman در مورد مقادیر احتمالی n برای یک n-gon تعمیم یافته پیروی می کند.

منبع

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

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

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

در ریاضیات ، ماتریس Hurwitz یا ماتریس Routh – Hurwitz ، در ماتریس پایداری مهندسی ، ماتریس مربع حقیقی ساختاری است که با ضرایب چند جمله ای حقیقی ساخته شده است.

فهرست

ماتریس هورویتس و معیار پایداری هورویتس [ ویرایش ]

یعنی با توجه به یک چند جمله ای حقیقی

$p (z) = a_ {0} z ^ {n} + a_ {1} z ^ {n-1} + \ cdots + a_ {n-1} z + a_ {n}$

$n \ n بار$ ماتریس مربع

$H = {\ start {pmatrix} a_ {1} & a_ {3} & a_ {5} & \ dots & \ dots & \ dots & 0 & 0 & 0 \\ a_ {0} & a_ {2} & a_ {4} &&&& vdots & \ vdots & \ vdots \\ 0 & a_ {1} & a_ {3} &&&& \ vdots & \ vdots & \ vdots \\\ vdots & a_ {0} & a_ {2} & \ ddots &&& 0 & \ vdots & \ vdots \\\ vdots & 0 & a_ {1 } && \ ddots && a_ {n} & \ vdots & \ vdots \\\ vdots & \ vdots & a_ {0} &&& \ ddots & a_ {n-1} & 0 & \ vdots \\\ vdots & \ vdots & 0 &&&& a_ {n-2} & a_ {n} & \ vdots \\\ vdots & \ vdots & \ vdots &&&& a_ {n-3} & a_ {n-1} & 0 \\ 0 & 0 & 0 & 0 & \ dots & \ نقطه & \ نقطه & a_ {n-4} & a_ {n -2} و a_ {n} \ end {pmatrix}}.$

ماتریس Hurwitz مربوط به چند جمله ای نامیده می شود $پ$ . توسط آدولف هورویتس در سال 1895 تاسیس شد که یک چند جمله ای حقیقی با آن است $a_ {0}> 0$ است پایدار (این است که، تمام ریشه های آن را قسمت حقیقی به شدت منفی) اگر و تنها اگر تمام اصل منجر افراد زیر سن قانونی از ماتریس $H (p)$ مثبت هستند:

${\ start {تراز شده} \ دلتا _ {1} (p) & = {\ start {vmatrix} a_ {1} \ end {vmatrix}} && = a_ {1}> 0 \\ [2mm] \ Delta _ {{ 2} (p) & = {\ start {vmatrix} a_ {1} & a_ {3} \\ a_ {0} & a_ {2} \\\ end {vmatrix}} && = a_ {2} a_ {1} - a_ {0} a_ {3}> 0 \\ [2mm] \ Delta _ {3} (p) & = {\ start {vmatrix} a_ {1} & a_ {3} & a_ {5} \\ a_ {0} & a_ {2} & a_ {4} \\ 0 & a_ {1} & a_ {3} \\\ end {vmatrix}} && = a_ {3} \ Delta _ {2} -a_ {1} (a_ {1} a_ { 4} -a_ {0} a_ {5})> 0 \ end {تراز شده}}$

و غیره خرد $\ دلتا _ {k} (ص)$ عوامل تعیین کننده هورویتس نامیده می شوند . به طور مشابه ، اگر ${\ displaystyle a_ {0} <0}$ در این صورت چند جمله ای پایدار است اگر و فقط در صورتی که خردسالان اصلی علائم متناوب دارند که با یک علامت منفی شروع می شوند.

ماتریس های پایدار هورویتس [ ویرایش ]

در تئوری مهندسی و پایداری ، یک ماتریس مربع $آ$ است که به نام ماتریس پایدار (یا گاهی اوقات یک ماتریس هورویتز ) اگر هر مقدار ویژه از $آ$ دارای قسمت حقیقی کاملاً منفی است ، یعنی

${\ displaystyle \ operatorname {Re} [\ lambda _ {i}] <0 \،}$

برای هر ارزش ویژه $\ lambda _ {i}$ . $آ$ همچنین ماتریس پایداری نامیده می شود ، زیرا در این صورت معادله دیفرانسیل است

${\ dot {x}} = تبر$

به صورت مجانبی پایدار است ، یعنی $x (t) \ تا 0$ مانند $t \ به \ بی فایده است.$

اگر $G (ها)$ A (ماتریس ارزش) است تابع انتقال ، و سپس $G$ Hurwitz نامیده می شود اگر قطب تمام عناصر از $G$ قسمت حقیقی منفی دارند توجه داشته باشید که لازم نیست که $G (ها) ،$ برای یک استدلال خاص $s ،$ ماتریس هورویتس باشد - حتی لازم نیست مربع باشد. ارتباط این است که اگر $آ$ یک ماتریس هورویتس است ، سپس سیستم پویا است

${\ dot {x}} (t) = Axe (t) + Bu (t)$

$y (t) = Cx (t) + Du (t) \ ،$

عملکرد انتقال Hurwitz دارد.

هر نقطه ثابت هذلولی (یا نقطه تعادل ) یک سیستم دینامیکی پیوسته بصورت محلی مجانبی پایدار است اگر و فقط اگر ژاکوبین سیستم دینامیکی در نقطه ثابت هریتس پایدار باشد.

ماتریس پایداری هورویتس قسمت مهمی از تئوری کنترل است . یک سیستم پایدار است اگر ماتریس کنترل آن ماتریس هورویتس باشد. مولفه های حقیقی منفی مقادیر ویژه ماتریس بازخورد منفی را نشان می دهند . به همین ترتیب ، اگر هر یک از مقادیر ویژه دارای اجزای حقیقی مثبت باشند ، یک سیستم ذاتاً ناپایدار است که بازخورد مثبت را نشان می دهد .

همچنین به مراجعه کنید

منبع

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

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

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

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

در ریاضیات ، در تئوری نمودار ، ماتریس همسایگی سیدل از یک نمودار ساده G بدون جهت ، یک ماتریس متقارن با یک ردیف و ستون برای هر راس است ، دارای 0 در مورب ، −1 برای موقعیت هایی که ردیف ها و ستون ها با رئوس مجاور مطابقت دارند و 1 برای موقعیت های مربوط به راس های غیر مجاور 1+. همچنین به آن ماتریس سیدل یا - نام اصلی آن - (،11،1،0) - ماتریس مجاورت گفته می شود . می توان آن را به عنوان نتیجه کم کردن تفسیر ماتریس مجاورت از G از ماتریس مجاورت مکمل از G .

های MultiSet از مقادیر ویژه این ماتریس به نام طیف سیدل .

ماتریس سیدل توسط JH van Lint و JJ Seidel در سال 1966 معرفی شد و به طور گسترده توسط سیدل و همکارانش مورد بهره برداری قرار گرفت.

ماتریس سیدل از G همچنین ماتریس مجاورت یک نمودار کامل امضا شده K G است که در آن لبه های G منفی هستند و لبه های موجود در G مثبت نیستند. همچنین ماتریس همجواری دو نمودار مرتبط با G و K G است .

خصوصیات ارزش ویژه ماتریس سیدل در مطالعه نمودارهای کاملا منظم ارزشمند است

منبع

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

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

نمودار کاملاً منظم

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

گراف پالی از سفارش 13، یک گراف به شدت به طور منظم با پارامترهای SRG (13،6،2،3).

خانواده های گراف توسط اتومورفیسم آنها تعریف شده است
فاصله گذرا	→	فاصله منظم	←	به شدت منظم
↓
متقارن (قوس-انتقالی)	←	t -transitive ، t ≥ 2		کج-متقارن
↓
(در صورت اتصال) راس و لبه انتقالی	→	لبه انتقالی و منظم	→	لبه دار
↓		↓		↓
راس-انتقالی	→	منظم	→	(اگر دو بخشی باشد ) بی قاعده است
↑
نمودار کیلی	←	متقارن صفر		نامتقارن

در تئوری گراف ، یک نمودار کاملاً منظم به شرح زیر تعریف شده است. بگذارید G = ( V ، E ) یک گراف منظم با V رئوس و درجه k باشد . G گفته می شود که اگر عدد صحیح λ و μ نیز وجود داشته باشد ، به شدت منظم است که:

هر دو راس مجاور λ همسایگان مشترک دارند.
هر دو راس غیر مجاور μ همسایه مشترک دارند.

گرافیکی از این نوع گاهی اوقات گفته می شود srg ( v ، k ، λ، μ). نمودارهای کاملاً منظمی توسط راج چاندرا بوز در سال 1963 معرفی شد . [1]

برخی از نویسندگان ، گراف هایی را که تعریف را به صورت پیش پا افتاده مطابقت می دهند ، از جمله گراف هایی که اتحاد جداگانه یک یا چند گراف کامل با اندازه یکسان ، [2] [3] و مکمل آنها ، گراف های کامل چند بخشی با مجموعه های مستقل با اندازه یکسان را حذف می کنند.

مکمل از SRG ( V ، K ، λ، μ) است نیز به شدت به طور منظم. این یک srg است

( v ، v − k −1 ، v −2−2 k + μ ، v −2 k + λ).

یک گراف کاملاً منظم یک گراف منظم با فاصله است که قطر 2 هر زمان μ غیر صفر باشد. این است گراف به صورت محلی خطی هر زمان که λ است.

فهرست

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

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

چهار پارامتر در یک srg ( v ، k ، λ ، μ) مستقل نیستند و باید از رابطه زیر پیروی کنند:

$(vk-1) \ mu = k (k- \ lambda -1)$

رابطه فوق را می توان به راحتی از طریق یک استدلال شمارش به شرح زیر بدست آورد:

راسهای نمودار را تصور کنید که در سه سطح قرار دارند. هر راس را به عنوان ریشه در سطح 0 انتخاب کنید. سپس k همسایگان آن در سطح 1 قرار می گیرند و سایر رئوس در سطح 2 قرار دارند.
رئوس سطح 1 مستقیماً به ریشه متصل هستند ، از این رو باید سایر همسایگان λ با ریشه مشترک باشند و این همسایگان مشترک نیز باید در سطح 1 باشند. از آنجا که هر راس دارای درجه k است ، $k- \ لامبدا -1$ لبه های باقی مانده برای هر گره سطح 1 برای اتصال به گره های سطح 2 وجود دارد. بنابراین ، وجود دارد $k \ بار (k- \ lambda -1)$ لبه های بین سطح 1 و سطح 2.
رئوس سطح 2 مستقیماً به ریشه متصل نیستند ، از این رو باید همسایه های μ با ریشه داشته باشند و این همسایگان مشترک باید همه در سطح 1 باشند. $(vk-1)$ رئوس در سطح 2 ، و هر یک به گره های μ در سطح 1 متصل می شوند ، بنابراین تعداد لبه ها بین سطح 1 و سطح 2 برابر است $(vk-1) \ بار \ mu$ .
با برابر کردن دو عبارت برای لبه ها بین سطح 1 و سطح 2 ، رابطه به شرح زیر است.

ماتریس همسایگی [ ویرایش ]

بگذارید ماتریس هویت را نشان دهم و اجازه دهید J ماتریس یکها را نشان دهد ، هر دو ماتریس ترتیب v . ماتریس مجاورت از ارضا نمودار به شدت منظم دو معادله. اولین:

$AJ = JA = kJ ،$

که بیان مجدد پیش پا افتاده ای از الزام نظم است. این نشان می دهد که k یک مقدار ویژه از ماتریس همجواری با بردار ویژه همه چیز است. دوم یک معادله درجه دوم است ،

${\ displaystyle {A} ^ {2} = k {I} + \ lambda {A} + \ mu ({JIA})}$

که بیانگر یک نظم قوی است. IJ عنصر توریم از سمت چپ می دهد تعدادی از مسیرهای دو مرحله ای از من به J . اولین اصطلاح RHS تعداد مسیرهای خود از i به i را می دهد ، یعنی k لبه های خارج و برگشت. اصطلاح دوم تعداد مسیرهای دو مرحله ای را نشان می دهد وقتی که i و j مستقیماً به هم متصل شوند. اصطلاح سوم هنگامی که i و j به هم متصل نیستند مقدار مربوطه را می دهد . از آنجا که این سه مورد متقابلاً منحصر به فرد و در مجموع طاقت فرسا هستند ، برابری افزودنی ساده به دنبال دارد.

برعکس ، گرافی که ماتریس مجاورت آن هر دو شرایط فوق را برآورده می کند و یک نمودار کامل یا صفر نیست ، یک نمودار کاملاً منظم است. [4]

مقادیر ویژه [ ویرایش ]

ماتریس مجاورت نمودار دقیقاً سه مقدار ویژه دارد :

k ، کثرت آن 1 است (همانطور که در بالا مشاهده می شود)
${\ displaystyle {\ frac {1} {2}} \ left [(\ lambda - \ mu) + {\ sqrt {(\ lambda - \ mu) ^ {2} +4 (k- \ mu)}} \ درست]،}$ ${\ frac {1} {2}} \ left [(v-1) - {\ frac {2k + (v-1) (\ lambda - \ mu)} {{\ sqrt {(\ lambda - \ mu) ^ {2} +4 (k- \ mu)}}}} \ راست]$
${\ displaystyle {\ frac {1} {2}} \ left [(\ lambda - \ mu) - {\ sqrt {(\ lambda - \ mu) ^ {2} +4 (k- \ mu)}} \ درست]،}$ که تعدد آن است راست] ${\ frac {1} {2}} \ left [(v-1) + {\ frac {2k + (v-1) (\ lambda - \ mu)} {{\ sqrt {(\ lambda - \ mu) ^ {2} +4 (k- \ mu)}}}} \ راست]$

همانطور که چندگانگی باید اعداد صحیح باشد، عبارت خود محدودیت بیشتر در مورد ارزش های ارائه V ، K ، μ ، و λ ، مربوط به اصطلاح شرایط کرین .

نمودارهایی کاملاً منظم که $2k + (v-1) (\ lambda - \ mu) = 0$ به دلیل ارتباط با ماتریس کنفرانس متقارن ، نمودار کنفرانس نامیده می شوند . پارامترهای آنها به کاهش می یابد

${\ text {srg}} \ چپ (v ، {\ tfrac {1} {2}} (v-1) ، {\ tfrac {1} {4}} (v-5) ، {\ tfrac {1} {4}} (v-1) \ راست).$

نمودارهایی کاملاً منظم که $2k + (v-1) (\ lambda - \ mu) \ neq 0$ دارای مقادیر ویژه عدد صحیح با چند برابر نابرابر هستند.

برعکس ، یک نمودار منظم متصل فقط با سه مقدار ویژه کاملاً منظم است. [5]

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

چرخه طول 5 SRG (5، 2، 0، 1) است.
گراف پترسن SRG (10، 3، 0، 1) است.
نمودار Clebsch به SRG (16، 5، 0، 2) است.
نمودار Shrikhande SRG (16، 6، 2، 2) است که نمی باشد نمودار فاصله-متعدی .
N × N مربع نمودار رخ ، به عنوان مثال، نمودار خط از گراف دوبخشی کامل و متعادل کننده K ، N، N ، یک SRG است ( N 2 ، 2 نفر - 2، N - 2، 2). پارامترهای n = 4 با پارامترهای نمودار Shrikhande منطبق هستند ، اما این دو نمودار غیر شکل نیستند.
نمودار خط از یک گراف کامل K N SRG (است ${\ displaystyle {\ binom {n} {2}} ، 2 (n-2) ، n-2،4}$ )
نمودار چانگ می SRG (28، 12، 6، 4)، همان نمودار خط K 8 ، اما این چهار نمودار، می ریخت است.
نمودار خط از یک چهارگوش تعمیم GQ (2، 4) SRG (27، 10، 1، 5) است. در واقع هر چهار ضلعی مرتب شده (s ، t) یک نمودار کاملاً منظم از این طریق می دهد: برای wit ، یک srg ((s + 1) (st + 1) ، s (t + 1) ، s-1 ، t 1+)
نمودار Schläfli SRG (27، 16، 10، 8) است. [6]
نمودار هافمن - سینگلتون یک srg است (50 ، 7 ، 0 ، 1).
نمودار Sims-Gewirtz یک نمودار (56 ، 10 ، 0 ، 2) است.
نمودار M22 با نام مستعار نمودار Mesner SRG (77، 16، 0، 4) است.
نمودار Brouwer – Haemers یک srg است (81 ، 20 ، 1 ، 6).
نمودار Higman – Sims یک srg است (100 ، 22 ، 0 ، 6).
نمودار مک لافلین محلی SRG (162، 56، 10، 24).
نمودار کامرون SRG (231، 30، 9، 3) است.
نمودار Berlekamp – van Lint – Seidel یک srg است (243 ، 22 ، 1 ، 2).
نمودار مک لافلین SRG (275، 112، 30، 56) است.
نمودار پالی از سفارش Q SRG (است س ، ( Q - 1) / 2، ( Q - 5) / 4، ( Q - 1) / 4). کوچکترین نمودار Paley ، با q = 5 ، 5 دور است (در بالا).
نمودارهای خود-مکمل قوسی-انتقالی کاملا منظم هستند.

اگر نمودار و مکمل آن به هم متصل شوند ، یک نمودار کاملاً منظم ابتدایی نامیده می شود . تمام نمودارهای فوق ابتدایی هستند ، در غیر این صورت μ = 0 یا λ = k.

مشکل 99 نمودار Conway خواستار ساخت srg است (99 ، 14 ، 1 ، 2). مشخص نیست که گرافی با این پارامترها وجود دارد یا خیر و جان هورتون کانوی جایزه ای 1000 دلاری برای حل این مشکل پیشنهاد داده است. [7]

نمودارهای بدون مثلث ، نمودارهای مور و نمودارهای ژئودتیک [ ویرایش ]

نمودارهای کاملاً منظم با λ = 0 مثلث آزاد هستند . جدا از نمودارهای کامل در کمتر از 3 راس و همه نمودارهای کامل و کامل ، هفت نمودار ذکر شده در بالا (پنج ضلعی ، پیترسن ، کلیبش ، هافمن-سینگلتون ، گویرتز ، مسنر-M22 و هیگمن-سیمز) تنها موارد شناخته شده هستند. نمودارهای کاملاً منظم با λ = 0 و μ = 1 نمودارهای مور با اندازه 5 هستند. باز هم سه نمودار فوق (پنج ضلعی ، پیترسن و هافمن-سینگلتون) ، با پارامترهای (5 ، 2 ، 0 ، 1) ، (10 ، 3 ، 0 ، 1) و (50 ، 7 ، 0 ، 1) ، تنها موارد شناخته شده هستند. تنها مجموعه ممکن دیگر از پارامترهای ارائه دهنده نمودار مور (3250 ، 57 ، 0 ، 1) است. اگر چنین گرافی وجود داشته باشد ، مشخص نیست و اگر چنین است ، منحصر به فرد است یا نه. [8]

به طور کلی ، هر نمودار کاملاً منظمی با $\ mu = 1$ یک نمودار ژئودتیک است ، گرافی که در آن هر دو رئوس کوتاهترین مسیر بدون وزنه را دارد . [9] تنها نمودارهای کاملاً منظم شناخته شده با $\ mu = 1$ نمودارهای مور هستند. وجود چنین گرافی امکان پذیر نیست $\ lambda = 1$ ، اما سایر ترکیبات پارامترها مانند (400 ، 21 ، 2 ، 1) هنوز منتفی نیستند. با وجود تحقیقات مداوم در مورد خواصی که یک نمودار کاملاً منظم با آنها دارد $\ mu = 1$ باید، [10] [11] از آن است که آیا هر موجود و یا حتی اینکه آیا تعداد آنها محدود است شناخته شده نیست. [9]

منبع

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

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

گراف منتظم

خانواده های گراف توسط اتومورفیسم آنها تعریف شده است
فاصله گذرا	→	فاصله منظم	←	به شدت منظم
↓
متقارن (قوس-انتقالی)	←	t -transitive ، t ≥ 2		کج-متقارن
↓
(در صورت اتصال) راس و لبه انتقالی	→	لبه انتقالی و منظم	→	لبه دار
↓		↓		↓
راس-انتقالی	→	منظم	→	(اگر دو بخشی باشد ) بی قاعده است
↑
گراف کیلی	←	متقارن صفر		نامتقارن

در نظریه گراف ، یک گراف منظم است گراف که در آن هر راس به همان تعداد از همسایه ها؛ یعنی هر راس از درجه یا ظرفیت بالایی برخوردار است . گراف جهتدار منظم نیز باید شرایط قوی تر که برآورده indegree و outdegree از هر راس برابر با یکدیگر هستند. [1] یک گراف منظم با رئوس درجه $ک$ a نامیده می شود $ک$ گراف منظم یا گراف منظم درجه $ک$ . همچنین ، از لمس دست دادن ، یک گراف عادی از درجه فرد شامل تعداد راس های زوج خواهد بود.

گراف های منظم درجه حداکثر 2 به راحتی قابل طبقه بندی هستند: یک گراف 0 منظم شامل رئوس جدا شده ، یک گراف 1 منظم از لبه های جدا شده و یک نمودار 2 منظم از یک اتحاد جداگانه از چرخه ها و زنجیره های بی نهایت تشکیل شده است.

نمودار 3 منظم به عنوان نمودار مکعب شناخته می شود .

یک گراف کاملاً منظم یک نمودار منظم است که در آن هر جفت رأس مجاور به همان تعداد l همسایگان مشترک است و هر جفت رأس غیر مجاور تعداد n همسایگی مشترک دارد. کوچکترین نمودار است که به طور منظم اما به شدت منظم نیست هستند که گراف چرخه و گراف گردشی در 6 راس.

گراف کامل $K_ {m}$ برای هر راس کاملاً منظم است $متر$ .

قضیه ای از نش ویلیامز می گوید که هر $ک$ -گراف منظم روی رئوس 2 k + 1 دارای یک چرخه همیلتونی است .

0-گراف منظم
گراف 1-منظم
گراف 2-منظم
3-گراف منظم

فهرست

وجود [ ویرایش ]

کاملاً مشهور است [ نیاز به ذکر منبع ] است که شرایط لازم و کافی برای یک $ک$ گراف منظم مرتبه $n$ وجود داشته باش این است که $n \ geq k + 1$ و آن $nk$ یکنواخت است

${\ displaystyle {\ binom {n} {2}} = {\ dfrac {n (n-1)} {2}}}$ و مرتبه ${\ displaystyle k = n-1، n = k + 1}$ است. این حداقل است $n$ برای یک خاص $ک$ . همچنین توجه داشته باشید که اگر هر گراف منظمی نظم داشته باشد $n$ سپس تعداد یال وجود دارد ${\ displaystyle {\ dfrac {nk} {2}}}$ بنابراین ${\ displaystyle nk}$ باید یکنواخت باشد. در چنین شرایطی ساختن گراف های منظم با در نظر گرفتن پارامترهای مناسب برای گراف های چرخشی آسان است .

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

فرض کنید ماتریس مجاورت یک گراف . یک گراف منظم است اگر و فقط اگر ${\ textbf {j}} = (1 ، \ نقطه ، 1)$ یک IS بردار ویژه باشد. [2] مقدار ویژه آن درجه ثابت نمودار خواهد بود. بردارهای ویژه مربوط به سایر مقادیر ویژه متعامد هستند ${\ textbf {j}}$ ، بنابراین برای چنین بردارهای ویژه $v = (v_ {1} ، \ dots ، v_ {n})$ ، ما داریم $\ sum _ {i = 1} ^ {n} v_ {i} = 0$ .

یک نمودار منظم از درجه k همبند است اگر و فقط اگر مقدار ویژه k چند برابر باشد. جهت "فقط اگر" نتیجه قضیه Perron-Frobenius است . [2]

همچنین یک معیار برای گراف های منظم و همبند وجود دارد: یک گراف همبند و منظم است اگر و فقط اگر ماتریس آنهایی از J ، با $J _ {{ij}} = 1$ ، در جبر همسایگی گراف است (به معنی ترکیبی خطی از قدرت های A است ). [3]

بگذارید G یک گراف منظم k با قطر D و مقادیر ویژه ماتریس مجاورت باشد

${\ displaystyle k = \ lambda _ {0}> \ lambda _ {1} \ geq \ cdots \ geq \ lambda _ {n-1}}$ . G دو بخشی نیست ، پس

${\ displaystyle D \ leq {\ frac {\ log {(n-1)}} {\ log (\ lambda _ {0} / \ lambda _ {1})}} + 1.}$ [4]

نسل [ ویرایش ]

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

منبع

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

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

سوال امتحانی در مورد قطری کردن(1)

نتیجه تصویری برای diagonalized matrix

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

سوال امتحانی در مورد قطری کردن

نتیجه تصویری برای diagonalized matrix

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

مثال :معکوس ماتریس به روش گوس -جردن

نتیجه تصویری برای diagonalized matrix

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

یک تست در باره ی قطری کردن ماتریس

نتیجه تصویری برای diagonalized matrix

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

قطری کردن ماتریس

قطری کردن ماتریس:

مقادیر ویژه ماتریس را حساب کنید
مقادیر ویژه ماتریس را را روی قطر ماتریسیD که همرتبه با ماتریس داده شده است قرار دهید
برا ی هر مقدار ویژه یک بردار ویژه بدست آورید
بردار های ویژه بدست آمده را ستون ماتریس P قرار دهید(به ترتیبی که روی قطر قرار داده اید)
معکوس P را بدست آورید
$A=PDP^{-1}$
$P^{-1}AP=D$

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

فرانک هاری

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

فرانک هاری
فرانک هاری (چپ) و کلاوس واگنر در اوبروولفاخ ، 1972
بدنیا آمدن	11 مارس 1921 شهر نیویورک ، نیویورک ، ایالات متحده آمریکا
فوت کرد	4 ژانویه 2005 (83 ساله) Las Cruces ، نیومکزیکو ، ایالات متحده آمریکا
ملیت	آمریکایی
ماده آلما	دانشگاه کالج بروکلین کالیفرنیا ، برکلی
شناخته شده برای	نمودار Goldner – Harary تیک تاک انگشت تعمیم یافته هری
حرفه علمی
زمینه های	ریاضیات
مسسات	دانشگاه ایالتی میشیگان نیومکزیکو
مشاور دکترا	آلفرد الفوستر

فرانک هاری (11 مارس 1921 - 4 ژانویه 2005) ریاضیدان آمریکایی ، متخصص در تئوری نمودار بود . وی به عنوان یکی از "پدران" تئوری مدرن نمودار شناخته شد. [1] هاری استاد بیان روشن بود و همراه با دانشجویان دکترا بسیار اصطلاحات نمودارها را استاندارد کرد. وی دامنه این رشته را گسترش داد و شامل فیزیک ، روانشناسی ، جامعه شناسی و حتی انسان شناسی شد. هاری با ذکاوت و شوخ طبعی جدی ، مخاطبان را در تمام سطوح پیچیدگی ریاضی به چالش و سرگرم می کند. ترفند خاصی که وی به کار برد این بود که قضیه ها را به بازی تبدیل کند - به عنوان مثال ، دانش آموزان سعی می کنند برای ایجاد یک مثلث قرمز ، لبه های قرمز را به یک نمودار در شش رئوس اضافه کنند ، در حالی که گروه دیگری از دانش آموزان سعی کردند لبه ها را ایجاد کنند تا یک مثلث آبی ایجاد کنند (و هر لبه نمودار باید آبی یا قرمز باشد). به دلیل قضیه دوستان و غریبه ها ، یک تیم یا دیگری باید برنده شوند.

فهرست

بیوگرافی [ ویرایش ]

فرانک هاری در شهر نیویورک متولد شد ، بزرگترین فرزند خانواده ای از یهودیان مهاجر از سوریه و روسیه است . وی به ترتیب در سال 1941 و 1945 لیسانس و فوق لیسانس خود را از کالج بروکلین دریافت کرد [2] و دکترای خود را دریافت کرد. ، با سرپرست آلفرد الفوستر ، از دانشگاه کالیفرنیا ، برکلی در سال 1948.

قبل از شغل معلمی وی دستیار تحقیق در انستیتوی تحقیقات اجتماعی در دانشگاه میشیگان شد .

اولین نشریه هاری ، "حلقه های اتمی مانند بولین با رادیکال محدود" ، تلاش زیادی کرد تا در سال 1950 در مجله ریاضیات دوک قرار گیرد . این مقاله برای اولین بار در نوامبر 1948 به انجمن ریاضیات آمریکا ارسال شد ، سپس به ریاضیات دوک ارسال شد ژورنالی که سه بار در آن تجدید نظر شد ، قبل از اینکه دو سال بعد از ارسال اولیه منتشر شود. [ نیازمند منبع ] هاری کار تدریس خود را در دانشگاه میشیگان در سال 1953 آغاز کرد و در آنجا ابتدا استادیار بود ، سپس در سال 1959 دانشیار شد و در سال 1964 به عنوان استاد ریاضیات منصوب شد ، این سمت را تا سال 1986 حفظ کرد.

وی از سال 1987 استاد (و استاد برجسته برجسته ) در گروه علوم کامپیوتر در دانشگاه ایالتی نیومکزیکو در لاس کروسس بود . وی از بنیانگذاران مجله نظریه ترکیبی و مجله نظریه نمودار بود . [1]

در سال 1949 هاراری درباره ساختار جبری گره ها منتشر کرد . اندکی پس از این انتشار در سال 1953 هاری اولین کتاب خود را (به طور مشترک با جورج اولنبک) در مورد تعداد درختان حسیمی منتشر کرد . به دنبال این متن بود که وی شروع به شهرت جهانی برای کار خود در تئوری نمودار کرد. در سال 1965 اولین کتاب وی مدلهای ساختاری: مقدمه ای بر نظریه نمودارهای جهت دار منتشر شد و تا آخر عمر علاقه او به حوزه تئوری نمودار بود .

در حالی که کار خود را در تئوری نمودار در حدود سال 1965 آغاز کرد ، هاری خرید ملک در آن آربور را شروع کرد تا درآمد خانواده اش را تأمین کند. هاری و همسرش جین شش فرزند با هم داشتند ، میریام ، ناتالی ، جودیت ، توماس ، جوئل و چایا.

از سال 1973 تا 2007 هاراری به طور مشترک پنج کتاب دیگر نوشت که هر كدام در زمینه تئوری گراف بودند. هری در زمان قبل از مرگ خود ، به تحقیق و انتشار بیش از 800 مقاله (با حدود 300 همکار نویسنده مختلف) در ژورنال های ریاضی و سایر نشریات علمی ، بیش از هر ریاضیدان دیگری به غیر از پل اردوس ، در جهان سفر کرد. هری ضبط کرد که در 166 شهر مختلف در اطراف ایالات متحده و حدود 274 شهر در بیش از 80 کشور مختلف سخنرانی کرده است. هری خصوصاً افتخار می کرد که در شهرهای جهان سخنرانی کرده و با شروع هر حرف از حروف الفبا ، حتی "X" هنگام سفر به زانتن ، آلمان سخنرانی کرده است . هاری همچنین نقش کنجکاوی را در فیلم برنده جایزه Good Will Hunting بازی کرد. این فیلم فرمولهایی را که وی در مورد شمارش درختان منتشر کرده بود نشان می داد ، که ظاهراً از نظر شیطانی بسیار دشوار بودند. [3]

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

وی در مرکز پزشکی Memorial در لاس کروسس ، نیومکزیکو درگذشت . [4] هنگام مرگ وی در لاس کروسس ، اعضای دیگر گروه علوم کامپیوتر این ضرر را برای ذهن بزرگی احساس کردند که زمانی در کنار آنها کار می کرد. رئیس گروه علوم رایانه در زمان مرگ هاری ، دش رنجان چنین گفت: "دکتر هاری عالمی واقعی بود و عشق واقعی به نظریه نمودار داشت که منبع بی پایان کشف جدید ، زیبایی ، کنجکاوی ، شگفتی بود. و شادی برای او تا پایان زندگی ".

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

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

شمارش نمودار ، یعنی شمردن نمودارها از یک نوع مشخص. [5] وی نویسنده کتابی در این زمینه بود (Harary و Palmer 1973). مشکل اصلی این است که دو نمودار غیر همسان نباید دو بار شمرده شوند. بنابراین ، باید نظریه شمارش پولایا را تحت عمل گروهی اعمال کرد. هری در این امر خبره بود.
نمودار امضا . هاری این شاخه از نظریه گراف را اختراع کرد [6] [7] که از یک مشکل روانشناسی اجتماعی نظری که توسط روانشناس دوروین کارتورایت و هاری بررسی شده بود ، بوجود آمد . [8]
کاربردهای تئوری نمودار در زمینه های مختلف ، به ویژه در علوم اجتماعی مانند تئوری تعادل و تئوری مسابقات . [9] هاری یکی از نویسندگان اولین کتاب الکترونیکی جان ویلی ، نظریه نمودار و جغرافیا بود .

در میان بیش از 700 مقالات علمی Harary نوشت، دو همکاری شد با پل Erdős ، به Harary تعداد اردوش از 1. [10] او گسترده سخنرانی و لیست به ترتیب حروف الفبا از شهرستانها که در او سخن گفت نگه داشته شود.

ترین کتاب کلاسیک معروف Harary است نظریه گراف در سال 1969 منتشر شد و ارائه یک مقدمه عملی به حوزه نظریه گراف. بدیهی است که تمرکز هاری در این کتاب و در میان سایر انتشارات وی به کاربرد متنوع و متنوع نظریه گراف در سایر زمینه های ریاضیات ، فیزیک و بسیاری دیگر بود. برگرفته از مقدمه تئوری نمودار ، یادداشت های هاری ...

" ... کاربردهای تئوری نمودار در برخی از زمینه های فیزیک ، شیمی ، علوم ارتباطات ، فناوری رایانه ، مهندسی برق و عمران ، معماری ، تحقیقات عملیاتی ، ژنتیک ، روانشناسی ، جامعه شناسی ، اقتصاد ، مردم شناسی و زبان شناسی وجود دارد. " [11 ]

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

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

یکی از انگیزه های مطالعه تئوری نمودار کاربرد آن در جامعه شناسی است که توسط Jacob L. Moreno توصیف شده است . به عنوان مثال ماتریس مجاورت یک جامعه شناسی توسط لئون فستینگر استفاده شده است. [12] فستینگر نظریه نمودار شناسایی باند با اجتماعی محفل و مورد بررسی قرار قطر از مکعب های ماتریس مجاورت یک گروه برای شناسایی باندهای. هری با یان راس همراه شد تا در تشخیص کلیک فستینگر پیشرفت کند. [13]

پذیرش قدرت ماتریس مجاورت باعث شد هری و راس توجه داشته باشند كه می توان نمودار كامل را از مربع ماتریس مجاورت یك درخت بدست آورد . آنها با تکیه بر مطالعه خود در زمینه تشخیص کلیک ، دسته ای از نمودارها را توصیف کردند که ماتریس مجاورت مربع ماتریس مجاورت یک درخت است. [14]

اگر یک نمودار G مربع یک درخت باشد ، یک ریشه مربع درخت منحصر به فرد دارد
برخی از واژگان لازم برای درک این اثبات و روشهای استفاده شده در اینجا در کتاب مربع یک درخت Harary ارائه شده است :
نحوه تشخیص اینکه برخی از نمودارهای G مربع یک درخت است یا خیر .

اگر یک نمودار G کامل باشد یا 5 ویژگی زیر را برآورده کند ، G = T 2 است

(i) هر نقطه G همسایگی است و G متصل است.

(ii) اگر دو دسته فقط در یک نقطه b با هم ملاقات داشته باشند ، دسته سوم وجود دارد که آنها b را با آن تقسیم می کنند و دقیقاً یک نقطه دیگر.

(iii) یک مکاتبات 1-1 بین کلیک ها و نقاط چندکاره ای G وجود دارد ، به طوری که دسته C (b) مربوط به b دقیقاً به همان تعداد نقاط چند جمله ای تعداد کلیک ها است که شامل b است.

(چهارم) هیچ دو دسته بیش از دو نقطه با هم تلاقی ندارند.

(v) تعداد جفت دسته هایی که در دو نقطه جمع می شوند ، یک تعداد کمتر از تعداد دسته ها است.

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

مرحله 1: پیدا کردن تمام دسته های G.

مرحله 2: اجازه دهید دسته های G C 1 ، ... ، C n باشد و مجموعه ای از نقاط چند صفحه ای b 1 ، ... ، b n مربوط به این دسته ها را مطابق با شرط iii در نظر بگیرید. عناصر این مجموعه نکات منفرد T. هستند و تمام تقاطع های دوتایی n کلیک را پیدا کرده و با پیوستن به نقاط b i و b j توسط یک خط نمودار S را تشکیل می دهیم اگر و فقط اگر کلیک های مربوطه C i و C j در دو نقطه تلاقی کنید. S سپس یک درخت با شرایط v است.

مرحله 3: برای هر دسته C من از G، اجازه دهید N من می شود تعدادی از نقاط unicliqual. به درخت در مرحله 2 به دست آمده، ضمیمه N من نقاط پایانی به ب من ، به دست آوردن درخت T که ما به دنبال.

هنگامی که درخت مورد نظر را بدست آوردیم می توانیم یک ماتریس مجاور برای درخت T ایجاد کنیم و بررسی کنیم که آیا واقعاً برای اصلاح درخت مورد نظر ما مناسب است. مربع سازی ماتریس همجواری T باید یک ماتریس همجواری برای گرافی که با نمودار G که ما شروع کردیم یکسان نباشد ، بدست آورد. احتمالاً ساده ترین راه برای مشاهده این قضیه در عمل مشاهده مواردی است که هاری در The Square of a Tree ذکر می کند. به طور خاص مثال مورد بحث درخت مربوط به نمودار K 5 را توصیف می کند

" درختی را در نظر بگیرید كه از یك نقطه به همه نقاط دیگر متصل شده است. وقتی درخت مربع شد ، نتیجه نمودار كامل است. ما مایل به نشان دادن ... T 2 $=$ K 5 "

با مجذور ماتریس همجواری درخت قبلاً ذکر شده ، می توان مشاهده کرد که این قضیه در حقیقت درست است. ما همچنین می توانیم مشاهده کنیم که این الگوی تنظیم درختی که "یک نقطه به همه نقاط دیگر پیوسته باشد" همیشه درخت صحیح را برای تمام نمودارهای کامل به ارمغان می آورد.

کتابشناسی [ ویرایش ]

1965: (با رابرت ز. نورمن و دوروین کارت رایت) ، مدلهای ساختاری: مقدمه ای بر نظریه نمودارهای کارگردانی . نیویورک: ویلی MR 0184874
1967: تئوری نمودار و فیزیک نظری ، مطبوعات علمی MR 0232694
1969: تئوری نمودار ، آدیسون-وسلی MR 0256911
1971: (ویراستار با هربرت ویلف ) جنبه های ریاضی تجزیه و تحلیل شبکه های برق ، مجموعه مقالات SIAM-AMS ، جلد 3 ، انجمن ریاضی آمریکا MR 0329788
1973: (ویراستار) جهت های جدید در نظریه نمودارها: مجموعه مقالات کنفرانس سال 1971 آن آربر در تئوری نمودار ، دانشگاه میشیگان ، مطبوعات آکادمیک. MR 0340065
1973: (با Edgar M. Palmer) مطبوعات علمی شمارش گرافیکی MR 0357214
1979: (ویراستار) مباحث تئوری نمودار ، آکادمی علوم نیویورک MR 557879
1984: (با هر هج) مدلهای ساختاری در انسان شناسی ، مطالعات کمبریج در انسان شناسی اجتماعی و فرهنگی ، انتشارات دانشگاه کمبریج MR 0738630
1990: (با فرد باكلی ) فاصله در نمودارها ، پرسئوس پرس MR 1045632
1991: (با هر هژ) مبادله در اقیانوسیه: تحلیل نظری نمودار ، مطالعات آکسفورد در انسان شناسی اجتماعی و فرهنگی ، انتشارات دانشگاه آکسفورد .
2002: (با Sandra Lach Arlinghaus و William C. Arlinghaus) تئوری نمودار و جغرافیا: کتاب الکترونیکی تعاملی ، John Wiley and Sons MR 1936840
2007: (با Per Hage) شبکه های جزیره ای: ارتباطات ، خویشاوندی و ساختارهای طبقه بندی در اقیانوسیه (تحلیل ساختاری در علوم اجتماعی) ، انتشارات دانشگاه کمبریج.

منبع

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

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

نظریه نمودار طیفی

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

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

ماتریس همجواری یک گراف ساده یک ماتریس متقارن حقیقی است و بنابراین از لحاظ قائم قابل مورب است . مقادیر ویژه آن اعداد صحیح جبری حقیقی هستند .

در حالی که ماتریس همجواری به برچسب گذاری راس بستگی دارد ، طیف آن یک نمودار ثابت است ، اگرچه یک کامل نیست.

نظریه نمودار طیفی همچنین مربوط به پارامترهای نمودار است که از طریق تعدد مقادیر ویژه ماتریس های مرتبط با نمودار تعریف می شوند ، مانند شماره کالین دو وردیر .

فهرست

نمودارهای طیفی [ ویرایش ]

اگر ماتریس های همجواری نمودارها دارای چند مجموعه مقادیر ویژه برابر باشند ، به دو نمودار متغیر یا متناوب گفته می شود .

دو عدد نافی طیفی ، کوچکترین نمودارهای چند وجهی طیفی

نمودار Cospectral لازم نیست ریخت ، اما نمودار متناظر همیشه cospectral.

نمودارهای تعیین شده توسط طیف آنها [ ویرایش ]

یک نمودار $G$ گفته می شود اگر هر نمودار دیگری با همان طیف همان طیف آن تعیین شود $G$ یکدست است به $G$ .

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

گرافهای کامل .
درختان محدود مانند ستاره .

همسران طیفی [ ویرایش ]

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

كوچكترین جفت همسانهای طیفی { K 1،4 ، C 4 ∪ K 1 } است كه شامل ستاره 5 رأس و اتحاد نمودار چرخه 4 رأس و نمودار رأس است ، همانطور كه كولاتز و سینوگوویتز گزارش كرده اند [ 1] [2] در سال 1957.

کوچکترین جفت از چند وجهی آمپول cospectral هستند enneahedra با هر هشت رأس. [3]

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

تقریباً همه درختان طیفی هستند ، یعنی با رشد تعداد رأس ، کسری از درختانی که یک درخت بزرگ برای آنها وجود دارد به 1 رسیده است. [4]

یک جفت نمودار منظم زمانی هستند که فقط درصورتی که مکمل های آن ها طیفی باشد. [5]

یک جفت نمودار منظم فاصله ای هستند و فقط در صورتی که آرایه تقاطع آنها یکسان باشد.

نمودارهای طیفی را می توان با استفاده از روش Sunada نیز ساخت . [6]

یکی دیگر از منابع مهم نمودارهای طیفی ، نمودارهای هم خطی و نمودارهای تقاطع خط هندسه های خط نقطه هستند . این نمودارها همیشه طیف سنجی هستند اما غالباً غیرهم شکل هستند. [7]

نابرابری چیگر [ ویرایش ]

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

ثابت چیگر [ ویرایش ]

مقاله اصلی: ثابت چیگر (تئوری نمودار)

ثابت چیگر(همچنین Cheeger تعداد و یا تعداد ایزومتریک ) از یک نمودار اندازه گیری عددی یا نه یک گراف دارای یک "تنگنا" است. ثابت چیگر به عنوان معیار "تنگنا" در بسیاری از مناطق بسیار مورد توجه است: به عنوان مثال ، ساخت شبکه های متصل به خوبی از رایانه ، جابجایی کارت و توپولوژی با ابعاد کم (به ویژه مطالعه 3- منیفولدهای هذلولی ).

به طور رسمی ، ثابت Cheeger h ( G ) یک نمودار G روی n رئوس به این صورت تعریف می شود

$h (G) = \ min_ {0 <| S | \ le \ frac {n} {2}} \ frac {| \ جزئی (S) |} {| S |} ،$

که در آن حداقل بیش از همه مجموعه ناتهی است S در اکثر N / 2 راس و ∂ ( S ) است مرز لبه از S ، یعنی مجموعه ای از لبه دقیقا با یک نقطه پایانی در S . [8]

نابرابری چیگر [ ویرایش ]

هنگامی که نمودار G است د به طور منظم، رابطه بین وجود دارد h( G ) و شکاف طیفی D - λ 2 از G . نابرابری ناشی از دودزیوک [9] و به طور مستقل آلون و میلمان [10] بیان می کند که [11]

${\ displaystyle {\ frac {1} {2}} (d- \ lambda _ {2}) \ leq h (G) \ leq {\ sqrt {2d (d- \ lambda _ {2})}}}.}$

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

نابرابری هافمن-دلسارت [ ویرایش ]

در نمودارهای منظم مقادیر ویژه ای برای مجموعه های مستقل وجود دارد که علت اصلی آن آلن جی هافمن و فیلیپ دلسارت است. [12]

فرض کنید که $G$ هست یک $ک$ نمودار منظم در $n$ رئوس با حداقل ارزش ویژه ${\ displaystyle \ lambda _ {\ mathrm {min}}}$ . سپس:

${\ displaystyle \ alpha (G) \ leq {\ frac {n} {1 - {\ frac {k} {\ lambda _ {\ mathrm {min}}}}}}}}$ جایی که ${\ displaystyle \ alpha (G)}$ شماره استقلال آن را نشان می دهد .

این محدودیت برای ایجاد اثبات جبری قضیه Erdős-Ko-Rado و آنالوگ آن برای تلاقی خانواده های زیرفضا در زمینه های محدود اعمال شده است . [13]

طرح کلی تاریخی [ ویرایش ]

نظریه نمودار طیفی در دهه 1950 و 1960 ظهور کرد. علاوه بر تحقیقات نظری نمودار در مورد رابطه بین خواص ساختاری و طیفی نمودارها ، منبع اصلی دیگر تحقیق در شیمی کوانتوم بود ، اما ارتباطات بین این دو خط کار تا دیرتر کشف نشد. [14] تک نگاری 1980 طیف نمودارها [15] توسط Cvetković ، Doob و Sachs خلاصه تقریباً تمام تحقیقات انجام شده در این منطقه است. در سال 1988 توسط نظرسنجی نتایج اخیر در نظریه طیف نمودار به روز شد . [16] نسخه سوم طیف نمودارها (1995) شامل خلاصه ای از مشارکت های اخیر بیشتر در این زمینه است.[14] تجزیه و تحلیل هندسی گسسته که توسط Toshikazu Sunada در دهه 2000ایجاد و توسعه یافته است، از نظر Laplacians گسسته مرتبط با نمودارهای وزن دار ، با تئوری نمودار طیفی سروکار دارد [17] و در زمینه های مختلف ، از جمله تجزیه و تحلیل شکل ، کاربرد پیدا می کند. در سالهای اخیر ، نظریه نمودار طیفی به نمودارهای متغیر راس که در بسیاری از برنامه های زندگی واقعی مشاهده می شوند ، گسترش یافته است. [18] [19] [20] [21]

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

منابع

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

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

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

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

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

در حالت خاص یک نمودار ساده محدود ، ماتریس همجواری یک ماتریس (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 توسط علی رضا نقش نیلچی |

جایگشت(11)

تغییر در محاسبات [ ویرایش ]

جایگزینی شماره گذاری [ ویرایش ]

یک روش برای نمایش جایگشتهای n ، یک عدد صحیح N با 0 ≤ N < n ! است ، به شرطی که روشهای مناسبی برای تبدیل بین عدد و نمایش جایگشت به عنوان یک ترتیب (ترتیب) مرتب داده شود. این به منزله جمع و جورترین نمایشی از جایگزینی های دلخواه است ، و در محاسبات به ویژه هنگامی جذابیت دارد که n به اندازه کافی کوچک باشد و بتوان N را در یک کلمه ماشین نگه داشت. این برای کلمات 32 بیتی به معنی n ≤ 12 و برای کلمات 64 بیتی به معنی n ≤ 20 است. تبدیل را می توان از طریق فرم میانی دنباله اعداد d n ، d n -1 انجام داد، ... ، d 2 ، d 1 ، جایی که d i یک عدد صحیح غیر منفی کمتر از i است (یکی ممکن است d 1 را حذف کند ، زیرا همیشه 0 است ، اما وجود آن توصیف تبدیل بعدی به جایگشت را آسان تر می کند) . اولین گام ، بیان ساده N در سیستم اعداد فاکتوریل است که فقط یک نمایش رادیکس مختلط است ، جایی که برای اعداد تا n ! مبنای ارقام متوالی n ، n - 1 ، ... ، 2 ، 1 است. مرحله دوم این توالی را به عنوان یک کد لمر تفسیر می کند یا (تقریباً معادل آن) به عنوان یک جدول وارونگی.

نمودار Rothe برای ${\ displaystyle \ sigma = (6،3،8،1،4،9،7،2،5)}$
σ i i	1	2	3	4	5	6	7	8	9	کد لمر
1	×	×	×	×	×	•				d 9 = 5
2	×	×	•							d 8 = 2
3	×	×		×	×		×	•		d 7 = 5
4	•									d 6 = 0
5		×		•						d 5 = 1
6		×			×		×		•	d 4 = 3
7		×			×		•			d 3 = 2
8		•								d 2 = 0
9					•					d 1 = 0
جدول وارونگی	3	6	1	2	4	0	2	0	0

در کد لمر برای جایگشت σ ، عدد d n نشان دهنده انتخابی است که برای ترم اول σ 1 ، عدد d n -1 نشان دهنده انتخابی است که برای ترم دوم σ 2 در بین عناصر n - 1 مجموعه باقی مانده است ، و غیره دقیق تر ، هر d n + 1 + i تعداد عناصر باقی مانده را دقیقاً کمتر از اصطلاح σ i می دهد . از آنجا که آن عناصر باقی مانده به عنوان برخی از اصطلاحات بعدی σ j ، رقم تبدیل می شوندد N + 1- من شمارش معکوس ( من ، J ) که شامل من به عنوان شاخص کوچکتر (تعداد مقادیر J که

جایگشت(10)

< J و σ

جایگشت(10)

> σ J ). جدول برگردان برای σ کاملا مشابه است، اما در اینجا د N + 1- K شمارش تعداد وارونه (

جایگشت(10)

، J ) که در آن K = σ J به عنوان کوچکتر از دو مقدار ظاهر می شود در سفارش معکوس رخ می دهد.[46] هر دو رمزگذاری را می توان با نمودار n by n Rothe [47] (به نام هاینریش آگوست روت نامگذاری کرد) مشاهده کرد که در آن نقاط در ( i ، σ i ) ورودی های جایگشت را نشان می دهند و یک ضربدر در ( i ، σ j ) وارونگی را مشخص می کند ( i ، j ) ؛ با تعریف وارون سازی یک صلیب در هر مربعی ظاهر می شود که هم قبل از نقطه ( j ، σ j ) در ستون آن قرار داشته باشد و هم قبل از نقطه ( i ، σ i) در ردیف آن. کد Lehmer تعداد تلاقی ها را در ردیف های متوالی لیست می کند ، در حالی که جدول وارونگی تعداد صلیب ها را در ستون های متوالی لیست می کند. این فقط کد لمر برای جایگزینی معکوس است و بالعکس.

برای تبدیل م Leثر کد Lehmer d n ، d n -1 ، ...، d 2 ، d 1 به جایگزینی یک مجموعه مرتب S ، می توان با لیستی از عناصر S با ترتیب بیشتر شروع کرد ، و برای i افزایش از 1 تا N مجموعه ای σ من به عنصر در لیست است که توسط قبل د N + 1- من آنهایی که دیگر، و حذف آن عنصر از لیست. برای تبدیل یک جدول وارونگی d n ، d n -1 ، ...، d2 ، d 1 به جایگشت مربوطه ، می توان اعداد را از d 1 تا d n جابجا کرد در حالی که عناصر S را از بزرگترین به کوچکترین در توالی اولیه خالی وارد می کند. در مرحله با استفاده از عدد d از جدول وارونگی ، عنصر از S وارد توالی می شود در نقطه ای که قبل از آن عناصر d وجود دارد. متناوباً می توان اعداد را از جدول وارونگی و عناصر S به ترتیب مخالف پردازش کرد ، با یک ردیف از n شکاف خالی شروع کرد و در هر مرحله عنصر را از S قرار دادبه شکاف خالی که قبل از آن d جای دیگر خالی است ، بروید.

تبدیل اعداد طبیعی متوالی به سیستم اعداد فاکتوریل ، آن توالی ها را به ترتیب فرهنگ لغت تولید می کند (همانطور که در مورد هر سیستم اعداد ترکیبی رادیکس وجود دارد) ، و تبدیل بیشتر آنها به جایگشتی ها ، ترتیب لغت نامه را حفظ می کند ، به شرطی که از تفسیر کد Lehmer استفاده شود (با استفاده از جداول وارون سازی ، یک ترتیب متفاوت بدست می آید ، جایی که فرد با مقایسه جایگزینی ها بر اساس مکان ورودی های آنها شروع می کند 1 به جای ارزش ورودی های اول آنها). مجموع اعداد در نمایش سیستم تعداد فاکتوریل ، تعداد وارون های جایگشت را نشان می دهد و برابری آن جمع ، امضا را می دهد.از جایگشت. علاوه بر این ، موقعیت صفرها در جدول وارونگی مقادیر حداکثر چپ به راست جایگشت را نشان می دهد (در مثال 6 ، 8 ، 9) در حالی که موقعیت صفرها در کد لمر موقعیت های سمت راست است حداقل به سمت چپ (در مثال 4 ، 8 ، 9 از مقادیر 1 ، 2 ، 5 قرار دارد) ؛ این اجازه می دهد تا توزیع چنین موارد اضافی را در میان تمام جایگشت ها محاسبه کند. یک جایگشت با کد Lehmer به د N ، D N -1 ، ...، د 2 ، د 1 است صعود N - من اگر و تنها اگر د من ≥ د i + 1 ام .

الگوریتم های ایجاد جایگشت [ ویرایش ]

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

یک روش واضح برای تولید جایگزارهای n تولید مقادیر برای کد Lehmer (احتمالاً با استفاده از نمایش عدد فاکتوریل سیستم عدد صحیح تا n !) و تبدیل آن به جایگشت های مربوطه است. با این حال ، مرحله دوم ، گرچه ساده است ، اما به سختی قابل پیاده سازی است ، زیرا به هر عملیات انتخاب از یک دنباله و حذف از آن ، در موقعیت دلخواه نیاز به n دارد. از نمایندگی آشکار از دنباله به عنوان یک آرایه یا یک لیست پیوندی ، هر دو نیاز به (به دلایل مختلف) در مورد N 2 /4 عملیات به انجام تبدیل. با nبه احتمال زیاد نسبتاً کوچک باشد (به خصوص اگر تولید همه جایگشت ها مورد نیاز باشد) که مسئله زیادی نیست ، اما مشخص می شود که هم برای نسل تصادفی و هم برای سیستماتیک گزینه های ساده ای وجود دارد که عملکرد به مراتب بهتری دارند. به همین دلیل استفاده از یک ساختار داده ویژه که امکان انجام تبدیل از کد Lehmer به جایگشت را در زمان O ( n log n ) فراهم می کند ، اگرچه مطمئناً امکان پذیر به نظر نمی رسد .

جایگزینی های ایجاد شده تصادفی [ ویرایش ]

مقاله اصلی: زدن فیشر – یتس

برای ایجاد جایگشتهای تصادفی از یک دنباله معین از مقادیر n ، تفاوتی نمی کند که کسی یک جایگشت تصادفی انتخاب شده از n را برای دنباله اعمال کند ، یا یک عنصر تصادفی را از مجموعه جایگزینهای مجزا (چند مجموعه ای) دنباله انتخاب کند. این بدان دلیل است که ، حتی اگر در صورت مقادیر تکرار شده ، جایگزینهای متمایز زیادی از n وجود داشته باشد که منجر به همان دنباله جایگزین شود ، تعداد چنین جایگشتهایی برای هر نتیجه ممکن یکسان است. بر خلاف نسل سیستماتیک ، که به دلیل رشد عدد n برای n بزرگ غیرقابل اجرا می شود ، هیچ دلیلی وجود ندارد که فرض کنیم n برای نسل تصادفی کوچک باشد.

ایده اصلی برای ایجاد جایگشت تصادفی ، ایجاد تصادفی یکی از n است ! توالی های اعداد صحیح d 1 ، d 2 ، ... ، d n که 0 ≤ d i < i را برآورده می کنند (از آنجا که d 1 همیشه صفر است ممکن است حذف شود) و آن را از طریق مکاتبات ذهنی به جایگشت تبدیل کنید . برای مکاتبات اخیر می توان دنباله (معکوس) را به عنوان یک کد لمر تفسیر کرد ، و این یک روش تولید را برای اولین بار در سال 1938 توسط رونالد فیشر و فرانک یتس منتشر می کند . [48] در حالی که در آن زمان پیاده سازی رایانه مسئله ای نبود ، این روش برای تبدیل م .ثر از کد لمر به جایگشت از مشکل طرح شده در بالا رنج می برد. بعد از استفاده از: این را می توان با استفاده از یک مکاتبات مختلف دوسویی رفع د من برای انتخاب یک عنصر در میان من عناصر دنباله (برای کاهش مقادیر باقی مانده من )، به جای از بین بردن عنصر و تراکم توالی با تغییر کردن عناصر بیشتر یک مکان ، یک مبادلهعنصر با عنصر نهایی باقی مانده. بنابراین عناصر باقی مانده برای انتخاب در هر مقطع زمانی یک محدوده متوالی تشکیل می دهند ، حتی اگر ممکن است به همان ترتیب که در توالی اصلی اتفاق نمی افتد ، رخ دهند. نقشه برداری از توالی اعداد صحیح به جایگشتی ها تا حدودی پیچیده است ، اما می توان مشاهده کرد که هر جایگویی را دقیقاً به یک طریق و با یک القای فوری ایجاد می کند . هنگامی که عنصر انتخاب شده به عنوان عنصر نهایی باقی مانده باشد ، می توان عملیات مبادله را حذف کرد. این امر اغلب به اندازه کافی برای تضمین آزمایش وضعیت اتفاق نمی افتد ، اما عنصر نهایی باید در میان نامزدهای انتخاب گنجانده شود تا تضمین کند که همه جایگشت ها ایجاد می شود.

الگوریتم حاصل برای ایجاد جایگشت تصادفی را می توان به صورت زیر در کد شبه توصیف کرد : a[0], a[1], ..., a[n − 1]

برای  i  از  n به  پایین 2 انجام 
    d i element عنصر تصادفی {0 ، ... ، i - 1}
     مبادله  a [ d i ] و a [ i - 1]

این را می توان با مقداردهی اولیه آرایه به صورت زیر ترکیب کرد a[i] = i

برای  من  از 0 تا  n -1 انجام 
    d i +1 element عنصر تصادفی {0 ، ... ، i }
     a [ i ] ← a [ d i +1 ]
     a [ d i +1 ] ← i

اگر d i +1 = i باشد ، انتساب اول یک مقدار غیر اولیه را کپی می کند ، اما دوم آن را با مقدار صحیح i بازنویسی می کند .

با این حال ، فیشر-ییتس سریعترین الگوریتم برای ایجاد جایگشت نیست ، زیرا فیشر-ییتس اساساً یک الگوریتم متوالی است و رویه های "تقسیم و تسخیر" می توانند به طور موازی به همان نتیجه برسند. [49]

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

روشهای زیادی وجود دارد که به طور سیستماتیک تمام جایگشتهای یک توالی معین را تولید می کند. [50] یک الگوریتم کلاسیک ، ساده و انعطاف پذیر مبتنی بر یافتن جایگزینی بعدی در ترتیب فرهنگ لغت است ، در صورت وجود. این می تواند مقادیر تکراری را کنترل کند ، در این صورت هر جایگزینی چند مجموعه ای مشخص را یک بار ایجاد می کند. حتی برای جایگشتهای معمولی نیز نسبت به تولید مقادیر برای کد Lehmer به ترتیب واژه نامه (احتمالاً با استفاده از سیستم تعداد فاکتوریل ) و تبدیل آن به جایگشت ، کارایی به مراتب بیشتری دارد . این کار با مرتب سازی دنباله در (ضعیف) در حال افزایش آغاز می شودمرتبه (که از نظر واژگانی حداقل جایگزینی خود را می دهد) ، و سپس تا زمانی که پیدا شود ، به جایگزینی بعدی پیش می رود. این روش به نارایانا پاندیتا در هند در قرن 14 برمی گردد و به طور مکرر کشف می شود. [51]

الگوریتم زیر جایگزینی بعدی را از لحاظ لغوی پس از جایگویی معین ایجاد می کند. جایگزینی داده شده را در محل تغییر می دهد.

بزرگترین شاخص k را پیدا کنید به طوری که a [ k ] < a [ k + 1] . اگر چنین شاخصی وجود نداشته باشد ، جایگشت آخرین جایگزینی است.
بزرگترین شاخص l بزرگتر از k را پیدا کنید به طوری که a [ k ] < a [ l ] .
تعویض ارزش [ K ] با آن از [ L ].
معکوس دنباله از [ K + 1] تا و از جمله عنصر نهایی [ N ].

به عنوان مثال ، با توجه به توالی [1 ، 2 ، 3 ، 4] (که به ترتیب بیشتر می شود) و با توجه به صفر بودن شاخص ، مراحل به شرح زیر است:

صفحه اول K = 2، به دلیل 3 است که در یک شاخص قرار داده شده که ارضا شرط بزرگترین شاخص این است که هنوز کمتر از [ K + 1] است که 4.
شاخص l = 3 ، زیرا 4 تنها مقدار دنباله ای است که برای تأمین شرط a [ k ] < a [ l ] بزرگتر از 3 است .
مقادیر a [2] و a [3] عوض می شوند تا توالی جدید ایجاد شود [1،2،4،3].
توالی بعد از k -index a [2] به عنصر نهایی معکوس می شود. از آنجا که فقط یک مقدار پس از این شاخص نهفته است (3) ، توالی در این نمونه بدون تغییر باقی می ماند. بنابراین جانشین فرهنگ لغت حالت اولیه جایگزین می شود: [1،2،4،3].

به دنبال این الگوریتم ، جایگشت واژه شناسی بعدی [1،3،2،4] و جایگزینی 24 ام خواهد بود [4،3،2،1] که در آن نقطه a [ k ] < a [ k + 1] انجام می دهد وجود ندارد ، نشان می دهد که این آخرین جایگزینی است.

این روش با استفاده از حدود 3 مقایسه و 1.5 مبادله در هر تغییر ، در کل دنباله استهلاک می شود ، بدون احتساب نوع اولیه. [52]

تولید با حداقل تغییرات [ ویرایش ]

مقالات اصلی: الگوریتم Steinhaus – Johnson – Trotter و الگوریتم Heap

یک جایگزین برای الگوریتم فوق ، الگوریتم Steinhaus – Johnson – Trotter ، نظمی را بر روی همه جایگشت های یک توالی معین با ویژگی ایجاد می کند که هر دو تغییر مکان متوالی در خروجی آن با تعویض دو مقدار مجاور متفاوت است. این دستور در مورد جایگشت ها برای زنگوله های انگلیسی قرن 17 شناخته می شد ، که در میان آنها به "تغییرات ساده" معروف بود. یکی از مزایای این روش این است که تغییر اندک از یک جایگزینی به روش دیگر اجازه می دهد تا روش در زمان ثابت در هر جایگزینی پیاده سازی شود. همین امر همچنین می تواند با رد کردن از هر جایگزینی خروجی دیگر ، به راحتی زیرمجموعه های حتی تغییر مکان ها را باز هم در زمان ثابت در هر جایگزینی ایجاد کند. [51]

یک جایگزین به Steinhaus جانسون-تروتر است الگوریتم هیپ ، [53] با گفت رابرت Sedgewick در سال 1977 به سریعترین الگوریتم تولید جایگشت در برنامه های کاربردی. [50]

شکل زیر خروجی هر سه الگوریتم فوق الذکر را برای تولید همه جایگشتهای طول نشان می دهد {\ displaystyle n = 4} $n = 4$ ، و شش الگوریتم اضافی که در ادبیات شرح داده شده است.

ترتیب همه جایگشتهای طول $n = 4$ تولید شده توسط الگوریتم های مختلف جایگزینی ها به صورت رنگی تنظیم شده است 1 ، 2 ، 3 ، 4 . [54]

سفارش واژه نامه نویسی؛
الگوریتم Steinhaus – Johnson – Trotter .
الگوریتم Heap ؛
الگوریتم جابجایی ستاره ای ارلیخ: [51] در هر مرحله ، ورودی اول جایگشت با ورودی بعدی رد و بدل می شود.
الگوریتم برگشت پیشوند Zaks: [55] در هر مرحله ، پیشوند جایگشت فعلی معکوس می شود تا جایگشت بعدی بدست آید.
الگوریتم Sawada-Williams: [56] هر تغییر یا تغییر با چرخش قبلی با یک چرخش چپ چرخشی به یک موقعیت ، یا با تبادل دو ورودی اول متفاوت است.
الگوریتم کوربت: [57] هر تغییر مکان با تغییر چپ چرخشی برخی از پیشوندها با یک موقعیت با قبلی متفاوت است.
ترتیب تک آهنگ: [58] هر ستون یک تغییر چرخشی از ستون های دیگر است.
کد خاکستری تک آهنگ: [58] هر ستون یک تغییر چرخشی از ستون های دیگر است ، به علاوه هر دو تغییر مکان متوالی فقط در یک یا دو جابجایی متفاوت است.

جایگزینی های میاندریک [ ویرایش ]

سیستم Meandric منجر به جایگشت meandric ، زیر مجموعه ای خاص از جایگشت های متناوب . جایگزینی جایگزین مجموعه {1 ، 2 ، ... ، 2 n } جایگزینی حلقوی است (بدون هیچ نقطه ثابت) به گونه ای که ارقام در شکل علامت چرخه ای بین اعداد صحیح فرد و زوج متناوب است. جابجایی های میاندریک در تحلیل ساختار ثانویه RNA مفید هستند. همه جایگزین های جایگزین میاندریک نیستند. از یک تغییر الگوریتم Heap برای تولید همه جایگزینهای متناوب سفارش n (یعنی طول 2 n ) بدون تولید همه (2 n ) استفاده شده است! جایگشت ها [59] [ منبع غیر قابل اعتماد؟ ] تولید این جایگزین های جایگزین قبل از آنکه مورد تجزیه و تحلیل قرار گیرد ، مورد نیاز است تا مشخص شود که آیا پیچ و خم هستند یا نه.

الگوریتم بازگشتی است. جدول زیر یک مرحله از مراحل را نشان می دهد. در مرحله قبل ، همه جایگزینی های جایگزین طول 5 ایجاد شده است. سه نسخه از هر یک از اینها "6" به انتهای سمت راست اضافه شده است ، و سپس یک جابجایی متفاوت شامل این آخرین ورودی و یک ورودی قبلی در یک موقعیت زوج اعمال می شود (از جمله هویت ؛ یعنی بدون جابجایی).

مجموعه های قبلی	جابجایی ارقام	جایگشتهای جایگزین
1-2-3-4-5-6		1-2-3-4-5-6
	4 ، 6	1-2-3-6-5-4
	2 ، 6	1-6-3-4-5-2
1-2-5-4-3-6		1-2-5-4-3-6
	4 ، 6	1-2-5-6-3-4
	2 ، 6	1-6-5-4-3-2
1-4-3-2-5-6		1-4-3-2-5-6
	2 ، 6	1-4-3-6-5-2
	4 ، 6	1-6-3-2-5-4
1-4-5-2-3-6		1-4-5-2-3-6
	2 ، 6	1-4-5-6-3-2
	4 ، 6	1-6-5-2-3-4

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

از جا به جایی ها در م inter لفه interleaver الگوریتم های تشخیص و اصلاح خطا استفاده می شود ، مانند کدهای توربو ، به عنوان مثال استاندارد مخابراتی تلفن همراه 3GPP Long Term Evolution از این ایده ها استفاده می کند (به مشخصات فنی 3GPP 36.212 [60] مراجعه کنید ). چنین کاربردهایی این س theال را مطرح می کند که تولید سریع جایگزینهایی که خاصیتهای مطلوبی را برآورده می کنند ، است. یکی از روش ها براساس چند جمله ای جایگشت است . همچنین به عنوان پایه ای برای هش کردن مطلوب در Unique Permutation Hashing. [61]

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

جایگشت(10)

وارون سازی [ ویرایش ]

مقاله اصلی: وارونگی (ریاضیات گسسته)

در پازل 15 هدف این است که مربع ها را به ترتیب صعودی بدست آورید. حل موقعیت های اولیه که تعداد معکوس وارون داشته باشند غیرممکن است. [43]

وارونگی از یک جایگشت σ یک جفت است ( من ، J ) از مواضع که در آن نوشته از یک جایگشت در مقابل عبارتند از: $من <j$ و ${\ displaystyle \ sigma _ {i}> \ sigma _ {j}}$ . [44] بنابراین نزول فقط وارونگی در دو موقعیت مجاور است. به عنوان مثال ، جایگزینی σ = 23154 دارای سه وارونه است: (1 ، 3) ، (2 ، 3) و (4 ، 5) ، برای جفت ورودی (2 ، 1) ، (3 ، 1) و ( 5 ، 4)

گاهی اوقات یک وارونگی به عنوان جفت مقادیر ( σ i ، σ j ) تعریف می شود که ترتیب آنها معکوس می شود. این برای تعداد وارونگی تفاوتی ایجاد نمی کند و این جفت (معکوس) نیز برای معکوس معکوس σ -1 یک معکوس است . تعداد وارونگی ها معیار مهمی برای درجه نامناسب بودن ورودی های جایگشت است. برای σ و برای σ −1 یکسان است . برای جایگزینی با وارونه k به ترتیب (یعنی تبدیل آن به جایگویی هویت) ، با اعمال پی در پی (ضرب راست با)جابجایی های مجاور ، همیشه ممکن است و به دنباله ای از k چنین عملیاتی نیاز دارد. علاوه بر این ، هر انتخاب معقول برای جابجایی های مجاور کارساز خواهد بود: کافی است در هر مرحله جابجایی i و i + 1 را انتخاب کنید جایی که من نزول جایگویی است که تاکنون اصلاح شده است (بنابراین جابجایی این نزول خاص را حذف می کند ، اگرچه ممکن است نزولات دیگری ایجاد کند). این بدان دلیل است که با استفاده از چنین جابجایی تعداد وارونگی 1 کاهش می یابد. تا زمانی که این عدد صفر نباشد ، جایگزینی هویت نیست ، بنابراین حداقل یک نزول دارد. مرتب سازی حباب و مرتب سازی درجمی تواند به عنوان موارد خاصی از این روش تفسیر شود تا یک توالی به نظم درآید. اتفاقاً این رویه ثابت می کند که هر جایگزینی σ را می توان به عنوان محصولی از جابجایی های مجاور نوشت. زیرا این ممکن است به سادگی هر توالی از چنین انتقال هایی را که σ را به هویت تبدیل می کند معکوس کند. در حقیقت ، با برشمردن تمام توالی های جابجایی های مجاور که می توانند σ را به هویت تبدیل کنند ، (پس از وارونه سازی) لیست کاملی از تمام عبارات با طول حداقل نوشتن σ به عنوان محصول جابجایی های مجاور بدست می آید.

تعداد جایگشت های n با وارون k با یک عدد ماهونی بیان می شود ، [45] این ضریب X k در انبساط محصول است.

${\ displaystyle \ prod _ {m = 1} ^ {n} \ sum _ {i = 0} ^ {m-1} X ^ {i} = 1 \ چپ (1 + X \ راست) \ چپ (1+) X + X ^ {2} \ راست) \ cdots \ چپ (1 + X + X ^ {2} + \ cdots + X ^ {n-1} \ راست) ،}$

که (با q جایگزین X ) به عنوان q-factorial [ n ] q نیز شناخته می شود ! . گسترش محصول در گردنبند (ترکیبی) ظاهر می شود .

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

جایگشت(9)

نمایش ماتریس [ ویرایش ]

ترکیب جایگشت ها مربوط به ضرب ماتریس های جایگشت است.

در واقع می توان یک جایگشت از {1، 2، ...، نشان دهنده N } به عنوان یک نفر × N ماتریس . دو راه طبیعی برای انجام این کار، اما تنها یک که ضرب ماتریس مربوط به ضرب جایگشت در جهت همان وجود دارد: این یکی که همکاران به است σ ماتریس M که ورود M من ، J 1 است اگر من = σ ( j ) ، و در غیر این صورت 0. ماتریس حاصل دقیقاً یک ورودی 1 در هر ستون و در هر ردیف دارد و به آن ماتریس جایگشت می گویند .
در اینجا لیستی از این ماتریس ها برای جایگزینی های 4 عنصر وجود دارد. جدول Cayley در سمت راست این ماتریس ها را برای جایگزینی 3 عنصر نشان می دهد.

لما transition گذار Foata [ ویرایش ]

بین علامت گذاری چرخه یک خطی و متعارف رابطه وجود دارد. جایگشت را در نظر بگیرید ${\ displaystyle (\، 2 \،) (\، 3 \، 1 \،)}$ ، در علامت گذاری متعارف متعارف ، اگر پرانتزهای چرخه آن را پاک کنیم ، جایگشت را بدست می آوریم ${\ displaystyle (2،3،1)}$ در علامت گذاری یک خط لما transition گذار Foata ماهیت این نامه نگاری را به عنوان یک انتخاب در مجموعه n- جایگزینی ها (به خودی خود) مشخص می کند. [39] ریچارد پی. استنلی این نامه نگاری را انتخاب اساسی می نامد . [25]

اجازه دهید $f$ تحول در پرانتزها باشد. معکوس $q = f (p)$ کمی شهودی است. شروع با علامت گذاری یک خط $q = q_ {1} q_ {2} \ cdots q_ {n}$ ، اولین چرخه در علامت گذاری چرخه متعارف باید با شروع شود $q_ {1}$ . به شرطی که عناصر بعدی کوچکتر از باشند $q_ {1}$ ، ما در یک چرخه هستیم. چرخه دوم با کوچکترین شاخص شروع می شود $ج$ به طوری که $q_ {j}> q_ {1}$ . به عبارت دیگر، $q_ {j}$ بزرگتر از هر چیز دیگری است که در سمت چپ آن قرار دارد ، بنابراین آن را حداکثر چپ به راست می نامند . هر چرخه در نماد چرخه متعارف با حداکثر چپ به راست شروع می شود. [39]

به عنوان مثال ، در علامت گذاری یک خطی ${\ displaystyle (3،1،2،5،4،8،9،7،6)}$ ، 5 اولین عنصر بزرگتر از 3 است ، بنابراین اولین چرخه باید باشد ${\ displaystyle (\ ، 3 \ ، 1 \ ، 2 \ ،)}}$ . سپس 8 عنصر بعدی بزرگتر از 5 است ، بنابراین چرخه دوم بزرگتر است ${\ displaystyle (\ ، 5 \ ، 4 \ ،)}$ . از آنجا که 9 بزرگتر از 8 است ، ${\ displaystyle (\ ، 8 \ ،)}$ به خودی خود یک چرخه است. سرانجام ، 9 از همه عناصر باقی مانده در سمت راست خود بزرگتر است ، بنابراین آخرین چرخه است ${\ displaystyle (\ ، 9 \ ، 7 \ ، 6 \ ،)}$ .

به عنوان اولین نتیجه ، تعداد n-جایگشتهایی که دقیقاً k حداکثر چپ به راست دارند نیز با تعداد استرلینگ بدون علامت از نوع اول برابر است ، $c (n ، k)$ . علاوه بر این ، نقشه برداری Foata به یک n- جایگزینی با k- ضعف اعمال می شود و به n- جایگزین با k - 1 صعود. [39] به عنوان مثال ، (2) (31) = 321 دارای دو مورد ضعیف است (در شاخص 1 و 2) ، در حالی که f (321) = 231 دارای یک صعود است (در شاخص 1 ؛ یعنی از 2 به 3).

تغییر مجموعه های کاملاً مرتب شده [ ویرایش ]

در بعضی از برنامه ها ، عناصر مجموعه ای که جایگزین می شوند با یکدیگر مقایسه می شوند. این مستلزم آن است که مجموعه S دارای ترتیب کلی باشد تا بتوان هر دو عنصر را با هم مقایسه کرد. مجموعه های {1 ، 2 ، ... ، n } کاملاً با رابطه معمول "ordered" مرتب می شوند و بنابراین بیشترین استفاده را در این برنامه ها دارند ، اما به طور کلی ، هر مجموعه کاملاً مرتب شده ای انجام می شود. در این برنامه ها ، نمایش چیدمان مرتب از یک جایگزین برای صحبت در مورد موقعیت ها در یک جایگزینی مورد نیاز است .

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

صعودها ، نزول ها ، دویدن ها و موارد اضافی [ ویرایش ]

صعود از یک جایگشت σ از N هر موقعیت است من < N که در آن مقدار زیر بزرگتر از یک جریان است. است که، اگر σ = σ 1 σ 2 ... σ N ، پس از آن من صعود اگر σ من < σ من 1 .

به عنوان مثال ، جایگشت 3452167 دارای صعودها (در موقعیت های) 1 ، 2 ، 5 و 6 است.

به طور مشابه ، نزول موقعیت i < n با σ i > σ i +1 است ، بنابراین هر i با ${\ displaystyle 1 \ leq i <n}$ یا صعود است یا نزول σ است .

یک روند صعودی یک جایگزینی یک دنباله مجاور افزایش ناپاکی است که نمی تواند در هر دو طرف تمدید شود. این مربوط به یک دنباله حداکثر از صعودهای پی در پی است (ممکن است مورد آخر خالی باشد: بین دو نزول متوالی هنوز یک مسیر صعودی به طول 1 وجود دارد). در مقابل توالی افزایش از یک جایگشت لزوما به هم پیوسته: این یک افزایش توالی از عناصر به دست آمده از جایگشت با حذف ارزش ها در برخی از موقعیت های است. به عنوان مثال ، جایگزینی 2453167 دارای مسیرهای صعودی 245 ، 3 و 167 است ، در حالی که دنباله رو به افزایش دارد 2367.

اگر یک جایگشت k - 1 نزول داشته باشد ، پس باید اتحادیه k دوام صعودی باشد. [40]

تعداد جایگشتهای n با k صعود (طبق تعریف) عدد اولری است $\ textstyle \ left \ langle {n \ atop k} \ right \ rangle$ ؛ این تعداد دگرگونی های n با k کاهش است . با این حال برخی از نویسندگان عدد اولری را تعریف می کنند $\ textstyle \ left \ langle {n \ atop k} \ right \ rangle$ به عنوان تعداد تغییراتی که با k اجرا می شود صعودی ، که مربوط به k - 1 نزول است. [41]

برتری یک جایگزینی σ 1 σ 2 ... σ n یک شاخص j است به طوری که σ j > j . اگر نابرابری سختگیرانه نباشد (یعنی σ j ≥ j ) ، آنگاه j را یک برآمدگی ضعیف می نامند . تعداد n- جایگشتهای دارای k منشأ با تعداد n- جایگشتهای k با نزول همزمان است. [42]

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

جایگشت(7)

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

جابجایی های چند مجموعه

اگر M محدود است MultiSet به ، و سپس یک جایگشت های MultiSet تنظیم دستور داد از عناصر است M در آن هر عنصر به نظر می رسد چند بار برابر دقیقا به تعدد آن در M . مقلوب یک کلمه با داشتن برخی از حروف تکرار یک مثال از یک جایگشت های MultiSet است. [e] اگر تعدد عناصر M (به ترتیب ترتیب گرفته شده) باشد $m_ {1}$ ، $m_ {2}$ ، ... ، $m_ {l}$ و مجموع آنها (یعنی اندازه M ) n است ، سپس تعداد جایگشتهای چند مجموعه ای M با ضریب چند جمله ای داده می شود ، [32]

${\ displaystyle {n \ m_ {1}، m_ {2}، \ ldots، m_ {l}} = {\ frac {n!} {m_ {1}! \، m_ {2}! \، \ cdots را انتخاب کنید \، m_ {l}!}} = {\ frac {\ left (\ sum _ {i = 1} ^ {l} {m_ {i}} \ right)!} {\ prod _ {i = 1} ^ {l} {m_ {i}!}}}.}$

به عنوان مثال ، تعداد آناگرام های مشخص کلمه MISSISSIPPI عبارت است از: [33]

${\ displaystyle {\ frac {11!} {1! \، 4! \، 4! \، 2!}} = 34650}$ .

K-جایگشت از MultiSet به M دنباله ای از طول است ک از عناصر M در آن هر عنصر به نظر می رسد چند بار کمتر یا برابر تعدد آن در M (یک عنصر تعداد تکرار ).

جایگزینی های دایره ای [ ویرایش ]

جابجایی ها ، هنگامی که به عنوان چیدمان در نظر گرفته می شوند ، گاهی اوقات به چیدمان های مرتب شده خطی گفته می شوند . در این تنظیمات یک عنصر اول ، یک عنصر دوم و غیره وجود دارد. اگر اگر ، اشیا به صورت دایره ای مرتب شده باشند که این ترتیب برجسته دیگر وجود نداشته باشد ، یعنی "اولین عنصر" در چیدمان وجود نداشته باشد ، هر عنصری را می توان شروع چیدمان در نظر گرفت. آرایش اشیا به صورت دایره ای را جایگشت های دایره ای می نامند . [34] [f] اینها را می توان به طور رسمی به عنوان کلاس های هم ارزی تغییر مکان های معمولی اشیا تعریف کرد ، برای رابطه هم ارزی تولید شده با انتقال عنصر نهایی چیدمان خطی به جلو.

اگر بتوان یکی را به دیگری چرخاند (یعنی چرخش بدون تغییر موقعیت نسبی عناصر) ، دو جایگشت دایره ای معادل است. دو جابجایی دایره ای زیر روی چهار حرف یکسان در نظر گرفته می شوند.

     1 4
   4 3 2 1
     2 3

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

     1 1
   4 3 3 4
     2 2

تعداد جایگزینی های دایره ای یک مجموعه S با n عنصر ( n - 1) است.

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

جایگشت(8)

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

تعداد جایگزینی های n شی objects مجزا n است !

تعداد n- جایگشتهای دارای k چرخه جدا از هم ، تعداد استرلینگ بدون علامت از نوع اول است که با c ( n ، k ) مشخص می شود . [35]

نوع جایگزینی [ ویرایش ]

چرخه های یک پارتیشن جایگشت مجموعه $S_ {n}$ بنابراین طول چرخه های یک جایگشت $\ سیگما$ تشکیل یک پارتیشن از N به نام نوع چرخه از $\ سیگما$ . برای هر نقطه ثابت σ ، "1" در نوع چرخه ، برای هر جابجایی "2" و غیره وجود دارد. نوع چرخه ${\ displaystyle \ beta = (\، 1 \، 2 \، 5 \،) (\، 3 \، 4 \،) (6 \، 8 \،) (\، 7 \،)}$ است (3،2،2،1) که گاهی اوقات به صورت فشرده تر به صورت [1 1 2 2 3 1 ] نوشته می شود.

شکل کلی آن است ${\ displaystyle [1 ^ {\ alpha _ {1}} 2 ^ {\ alpha _ {2}} \ dotsm n ^ {\ alpha _ {n}}]}$ ، جایی که $\ alpha _ {1} ، \ ldots ، \ alpha _ {n}$ تعداد چرخه های طول مربوطه است. تعداد جایگزینی های یک نوع خاص [36] است

${\ displaystyle {\ frac {n!} {1 ^ {\ alpha _ {1}} 2 ^ {\ alpha _ {2}} \ dotsm n ^ {\ alpha _ {n}} \ alpha _ {1}! \ alpha _ {2}! \ dotsm \ alpha _ {n}!}}}$ .

جایگزین های مزدوج [ ویرایش ]

به طور کلی ، ترکیب جایگزینی های نوشته شده در علامت گذاری چرخه از الگویی که به راحتی توصیف می شود پیروی نمی کند - چرخه های ترکیب می توانند متفاوت از ترکیبات باشند. با این حال ساختار چرخه در حالت خاص مخلوط جایگشت حفظ می شود $\ سیگما$ با جایگزینی دیگر $\ پی$ ، که به معنی تشکیل محصول است ${\ displaystyle \ pi \ sigma \ pi ^ {- 1}}$ . اینجا، ${\ displaystyle \ pi \ sigma \ pi ^ {- 1}}$ است مزدوج از $\ سیگما$ و علامت گذاری چرخه آن را می توان با در نظر گرفتن علامت چرخه بدست آورد $\ سیگما$ و درخواست کردن $\ پی$ به تمام ورودی های موجود در آن. [37] از این رو نتیجه می گیرد که دو جایگویی دقیقاً هنگامی که از نوع یکسانی باشند مزدوج هستند.

دستور جایگزینی [ ویرایش ]

ترتیب جایگشت $\ سیگما$ کوچکترین عدد صحیح مثبت m است به طوری که ${\ displaystyle \ sigma ^ {m} = \ mathrm {id}}$ . این کمترین مضرب طول چرخه های آن است. به عنوان مثال ، ترتیب ${\ displaystyle (\، 1 \، 3 \، 2) (\، 4 \، 5 \،)}$ است ${\ displaystyle 2 \ cdot 3 = 6}$ .

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

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

این نتیجه را می توان گسترش داد تا یک علامت ، نوشته شده اختصاص دهد ${\ displaystyle \ operatorname {sgn} \ sigma}$ ، به هر جایگزینی. ${\ displaystyle \ operatorname {sgn} \ sigma = + 1}$ اگر $\ سیگما$ حتی است و ${\ displaystyle \ operatorname {sgn} \ sigma = -1}$ اگر $\ سیگما$ عجیب است سپس برای دو جایگشت $\ سیگما$ و $\ پی$

${\ displaystyle \ operatorname {sgn} (\ sigma \ pi) = \ operatorname {sgn} \ sigma \ cdot \ operatorname {sgn} \ pi.}$

نتیجه می شود که ${\ displaystyle \ operatorname {sgn} \ چپ (\ sigma \ sigma ^ {- 1} \ راست) = + 1.}$

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

مطالب قدیمی‌تر

آموزش ریاضی

فهرست

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

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

گروه ماتریکس [ ویرایش ]

ماتریس تصادفی دو برابر [ ویرایش ]

خصوصیات جبری خطی [ ویرایش ]

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

تغییر سطرها و ستون ها [ ویرایش ]

جایگشت ردیف ها [ ویرایش ]

توضیح [ ویرایش ]

فرمهای محدود [ ویرایش ]

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

فهرست

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

جاسازی ها [ ویرایش ]

تقارن [ ویرایش ]

مسیرها و چرخه های همیلتون [ ویرایش ]

رنگ آمیزی [ ویرایش ]

خواص دیگر [ ویرایش ]

حدس رنگ آمیزی پیترسن [ ویرایش ]

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

فهرست

تاریخچه [ ویرایش ]

مکان و نظم [ ویرایش ]

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

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

منبع

فهرست

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

علائم تجزیه ای [ ویرایش ]

منبع

خصوصیات نمودارهای منظم تصادفی [ ویرایش ]

الگوریتم نمودارهای تصادفی منظم [ ویرایش ]

منبع

فهرست

رئوس محدود بر اساس درجه و قطر [ ویرایش ]

نمودارهای مور به عنوان قفس [ ویرایش ]

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

فهرست

ماتریس هورویتس و معیار پایداری هورویتس [ ویرایش ]

ماتریس های پایدار هورویتس [ ویرایش ]

همچنین به مراجعه کنید

فهرست

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

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

ماتریس همسایگی [ ویرایش ]

مقادیر ویژه [ ویرایش ]

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

نمودارهای بدون مثلث ، نمودارهای مور و نمودارهای ژئودتیک [ ویرایش ]

فهرست

وجود [ ویرایش ]

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

نسل [ ویرایش ]

فهرست

بیوگرافی [ ویرایش ]

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

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

کتابشناسی [ ویرایش ]

منبع

فهرست

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

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

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

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

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

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

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

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

طیف [ ویرایش ]

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

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

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

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

تغییر در محاسبات [ ویرایش ]

جایگزینی شماره گذاری [ ویرایش ]

الگوریتم های ایجاد جایگشت [ ویرایش ]

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

وارون سازی [ ویرایش ]

نمایش ماتریس [ ویرایش ]

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