کموتاتور (جابجا گر)

ن مقاله در مورد مفهوم ریاضی است. برای بخش الکتریکی، کموتاتور (الکتریکی) را ببینید . برای رابطه بین موجودات مزدوج متعارف ، به رابطه کموتاسیون متعارف مراجعه کنید . برای کاربردهای دیگر، Commutation را ببینید .

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

نظریه گروه

[ ویرایش ]

جابجا گر دو عنصر g و h از گروه G عنصر است

[ g ، h ] = g ^-1 h ^-1 gh .

این عنصر برابر با هویت گروه است اگر و فقط اگر g و h رفت و آمد کنند (یعنی اگر و فقط اگر gh = hg ).

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

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

[ g ، h ] = ghg ​​^-1 h^ -1 . [ 1 ] [ 2 ]

با استفاده از تعریف اول، این می تواند به صورت [ g^ -1 ، h^ -1 ] بیان شود .

هویت (نظریه گروهی)

[ ویرایش ]

هویت های کموتاتور ابزار مهمی در نظریه گروه هستند . [ 3 ] عبارت a x نشان دهنده مزدوج a با x است که به صورت x -1 ax تعریف شده است .

  1. {\displaystyle x^{y}=x[x,y].}
  2. {\displaystyle [y,x]=[x,y]^{-1}.}
  3. {\displaystyle [x,zy]=[x,y]\cdot [x,z]^{y}}و{\displaystyle [xz,y]=[x,y]^{z}\cdot [z,y].}
  4. {\displaystyle \left[x,y^{-1}\right]=[y,x]^{y^{-1}}}و{\displaystyle \left[x^{-1},y\right]=[y,x]^{x^{-1}}.}
  5. {\displaystyle \left[\left[x,y^{-1}\right],z\right]^{y}\cdot \left[\left[y,z^{-1}\right],x \right]^{z}\cdot \left[\left[z,x^{-1}\right],y\right]^{x}=1}و{\displaystyle \left[\left[x,y\right],z^{x}\right]\cdot \left[[z,x],y^{z}\right]\cdot \چپ[[y ,z],x^{y}\right]=1.}

هویت (5) پس از فیلیپ هال و ارنست ویت به نام هویت هال ویت نیز شناخته می شود . این یک آنالوگ نظری گروهی از هویت ژاکوبی برای کموتاتور نظری حلقه است (به بخش بعدی مراجعه کنید).

NB، تعریف فوق از مزدوج a توسط x توسط برخی از نظریه پردازان گروه استفاده می شود. [ 4 ] بسیاری از نظریه پردازان گروه دیگر مزدوج a توسط x را به عنوان xax -1 تعریف می کنند . [ 5 ] این اغلب نوشته می شودxالف{\displaystyle {}^{x}a}. هویت های مشابهی برای این کنوانسیون ها وجود دارد.

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

{\displaystyle (xy)^{2}=x^{2}y^{2}[y,x][[y,x],y].}

اگر زیر گروه مشتق شده مرکزی باشد، پس

{\displaystyle (xy)^{n}=x^{n}y^{n}[y,x]^{\binom {n}{2}}.}

نظریه حلقه

[ ویرایش ]

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

{\displaystyle [a,b]=ab-ba.}

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

ضد جابجا گر دو عنصر a و b یک حلقه یا جبر انجمنی با تعریف می شود

{\displaystyle \{a,b\}=ab+ba.}

گاهی اوقات

{\displaystyle [a,b]_{+}}برای نشان دادن anticommutator، در حالی که استفاده می شود

{\displaystyle [a,b]_{-}}سپس برای جابجا گراستفاده می شود. [ 6 ] ضد جابجا گرکمتر مورد استفاده قرار می گیرد، اما می توان از آن برای تعریف جبرهای کلیفورد و جبر جردن و در استخراج معادله دیراک در فیزیک ذرات استفاده کرد .

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

هویت (نظریه حلقه)

[ ویرایش ]

کموتاتور دارای ویژگی های زیر است:

هویت های لی-جبر

[ ویرایش ]

  1. {\displaystyle [A+B,C]=[A,C]+[B,C]}
  2. {\displaystyle [A,A]=0}
  3. {\displaystyle [A,B]=-[B,A]}
  4. {\displaystyle [A,[B,C]]+[B,[C,A]]+[C,[A,B]]=0}

رابطه (3) ضد جابجا گر نامیده می شود ، در حالی که (4) هویت ژاکوبی است .

هویت های اضافی

[ ویرایش ]

  1. {\displaystyle [A,BC]=[A,B]C+B[A,C]}
  2. {\displaystyle [A,BCD]=[A,B]CD+B[A,C]D+BC[A,D]}
  3. {\displaystyle [A,BCDE]=[A,B]CDE+B[A,C]DE+BC[A,D]E+BCD[A,E]}
  4. {\displaystyle [AB,C]=A[B,C]+[A,C]B}
  5. {\displaystyle [ABC,D]=AB[C,D]+A[B,D]C+[A,D]BC}
  6. {\displaystyle [ABCD,E]=ABC[D,E]+AB[C,E]D+A[B,E]CD+[A,E]BCD}
  7. {\displaystyle [A,B+C]=[A,B]+[A,C]}
  8. {\displaystyle [A+B,C+D]=[A,C]+[A,D]+[B,C]+[B,D]}
  9. {\displaystyle [AB,CD]=A[B,C]D+[A,C]BD+CA[B,D]+C[A,D]B=A[B,C]D+AC[B, D]+[A,C]DB+C[A,D]B}
  10. {\displaystyle [[A,C],[B,D]]=[[[A,B],C],D]+[[[B,C],D],A]+[[[C, D],A],B]+[[[D,A],B],C]}

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

{\displaystyle \operatorname {ad} _{A}:R\rightarrow R}داده شده توسط

{\displaystyle \operatorname {ad} _{A}(B)=[A,B]}.

به عبارت دیگر، نقشه آگهی A یک مشتق بر روی حلقه R تعریف می کند . هویت های (2)، (3) قوانین لایب نیتس را برای بیش از دو عامل نشان می دهند و برای هر اشتقاقی معتبر هستند. هویت های (4) - (6) را می توان به عنوان قوانین لایب نیتس نیز تفسیر کرد. هویت های (7)، (8) Z - دوخطی بودن را بیان می کنند .

از هویت (9)، می توان دریافت که جابجایی قدرت های عدد صحیح عناصر حلقه عبارت است از:

{\displaystyle [A^{N},B^{M}]=\sum _{n=0}^{N-1}\sum _{m=0}^{M-1}A^{n} B^{m}[A,B]B^{Nn-1}A^{Mm-1}=\sum _{n=0}^{N-1}\sum _{m=0}^{M-1}B^{n}A^{m}[A,B]A^{Nn-1}B^{Mm-1}}

برخی از هویت‌های فوق را می‌توان با استفاده از نماد ± زیرمجموعه بالا به آنتی‌کموتاتور تعمیم داد. [ 8 ] به عنوان مثال:

  1. {\displaystyle [AB,C]_{\pm }=A[B,C]_{-}+[A,C]_{\pm }B}
  2. {\displaystyle [AB,CD]_{\pm }=A[B,C]_{-}D+AC[B,D]_{-}+[A,C]_{-}DB+C[ A,D]_{\pm }B}
  3. {\displaystyle [[A,B],[C,D]]=[[[B,C]_{+},A]_{+},D]-[[[B,D]_{+} ,A]_{+},C]+[[[A,D]_{+},B]_{+},C]-[[A,C]_{+},B]_{+ },D]}
  4. {\displaystyle \left[A,[B,C]_{\pm }\right]+\left[B,[C,A]_{\pm }\right]+\left[C,[A,B ]_{\pm }\right]=0}
  5. {\displaystyle [A,BC]_{\pm }=[A,B]_{-}C+B[A,C]_{\pm }=[A,B]_{\pm }C\mp B[A,C]_{-}}
  6. {\displaystyle [A,BC]=[A,B]_{\pm }C\mp B[A,C]_{\pm }}

هویت های نمایی

[ ویرایش ]

حلقه یا جبری را در نظر بگیرید که در آن نمایی است هالف=انقضا⁡(الف)=1+الف+12!الف2+⋯{\displaystyle e^{A}=\exp(A)=1+A+{\tfrac {1}{2!}}A^{2}+\cdots }را می توان به طور معناداری تعریف کرد، مانند جبر Banach یا حلقه ای از سری های قدرت رسمی .

در چنین حلقه‌ای، لم هادامارد که برای کموتاتورهای تودرتو اعمال می‌شود، به دست می‌دهد:

{\textstyle e^{A}Be^{-A}\ =\ B+[A,B]+{\frac {1}{2!}}[A,[A,B]]+{\frac {1 {3!}}[A,[A,[A,B]]]+\cdots \ =\ e^{\operatorname {ad} _{A}}(B).}(برای آخرین عبارت، مشتق الحاقی را در زیر ببینید.) این فرمول زیربنای بسط Baker–Campbell–Hausdorff از log(exp( A ) exp( B )) است.

یک بسط مشابه، تغییردهنده گروهی عبارات را بیان می کند{\displaystyle e^{A}}(مشابه عناصر گروه لی ) از نظر یک سری جابجا گر تو در تو (براکت های لی)،

{\displaystyle e^{A}e^{B}e^{-A}e^{-B}=\exp \!\left([A,B]+{\frac {1}{2!}} [A{+}B,[A,B]]+{\frac {1}{3!}}\left({\frac {1}{2}}[A,[B,[B,A]]]+[A{+}B,[A{+}B,[A,B]]]\right)+\cdots \right )

حلقه ها و جبرهای درجه بندی شده

[ ویرایش ]

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

{\displaystyle [\omega ,\eta ]_{gr}:=\omega \eta -(-1)^{\deg \omega \deg \eta }\eta \omega .}

اشتقاق الحاقی

[ ویرایش ]

به خصوص اگر یکی با چند جابجا گر در یک حلقه R سر و کار داشته باشد ، نماد دیگری مفید خواهد بود. برای یک عنصر{\displaystyle x\in R}، نگاشت الحاقی را تعریف می کنیم{\displaystyle \mathrm {ad} _{x}:R\to R}توسط:

{\displaystyle \operatorname {ad} _{x}(y)=[x,y]=xy-yx.}

این نگاشت یک مشتق بر روی حلقه R است :

{\displaystyle \mathrm {ad} _{x}\!(yz)\ =\ \mathrm {ad} _{x}\!(y)\,z\,+\,y\,\mathrm {ad} _{x}\!(z).}

با هویت ژاکوبی ، آن نیز اشتقاقی بر عملیات کموتاسیون است:

{\displaystyle \mathrm {ad} _{x}[y,z]\ =\ [\mathrm {ad} _{x}\!(y),z]\,+\,[y,\mathrm {ad} } _{x}\!(z)].}

به عنوان مثال، با نوشتن چنین نگاشت هایی، به دست می آوریم

{\displaystyle \operatorname {ad} _{x}\operatorname {ad} _{y}(z)=[x,[y,z]\,]}و

{\displaystyle \operatorname {ad} _{x}^{2}\!(z)\ =\ \operatorname {ad} _{x}\!(\operatorname {ad} _{x}\!(z) )\ =\ [x،[x،z]\،].}ممکن است در نظر بگیریمالفد{\displaystyle \mathrm {ad} }خود به عنوان یک نقشه برداری،

{\displaystyle \mathrm {ad} :R\to \mathrm {End} (R)}، که

{\displaystyle \mathrm {End} (R)}حلقه ای از نگاشت از R به خود با ترکیب به عنوان عملیات ضرب است. سپسالفد{\displaystyle \mathrm {ad} }یک هممورفیسم جبر دروغ است که تغییر دهنده را حفظ می کند:

{\displaystyle \operatorname {ad} _{[x,y]}=\left[\operatorname {ad} _{x},\operatorname {ad} _{y}\right].}

در مقابل، همیشه هممورفیسم حلقه نیست : معمولا {\displaystyle \operatorname {ad} _{xy}\,\neq \,\operatorname {ad} _{x}\operatorname {ad} _{y}}.

قانون مولد لایب نیتس

[ ویرایش ]

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

{\displaystyle x^{n}y=\sum _{k=0}^{n}{\binom {n}{k}}\operatorname {ad} _{x}^{k}\!(y) \,x^{nk}.}

جایگزین کردن{\displaystyle x}توسط عملگر تمایز{\displaystyle \جزئی }، وy{\displaystyle y}توسط عملگر ضرب {\displaystyle m_{f}:g\mapsto fg}، دریافت می کنیم{\displaystyle \operatorname {ad} (\partial )(m_{f})=m_{\partial (f)}}و با اعمال هر دو طرف برای تابع g ، هویت به قانون معمول لایب نیتس برای مشتق n تبدیل می شود.{\displaystyle \partial ^{n}\!(fg)}.

همچنین ببینید

[ ویرایش ]

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

جنس هندسی

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

      در هندسه جبری ، جنس هندسی یک pg ثابت دوتایی پایه از انواع جبری و منیفولدهای پیچیده است .

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

      جنس هندسی را می توان برای واریته های پرتابی پیچیده غیر منفرد و به طور کلی برای منیفولدهای پیچیده به صورت عدد هاج h n ,0 (برابر h 0, n با دوگانگی Serre ) تعریف کرد، یعنی بعد سیستم خطی متعارف به اضافه یکی

      به عبارت دیگر، برای انواع V با بعد مختلط n ، تعداد n شکل‌های هولومورف مستقل خطی است که روی V یافت می‌شوند . [1] این تعریف، به عنوان بعد از

      H 0 ( Vn )

      سپس به هر میدان پایه منتقل می‌شود ، زمانی که Ω به عنوان شیف دیفرانسیل‌های کاهلر در نظر گرفته می‌شود و توان قدرت بیرونی (بالا) ، بسته خط متعارف است .

      جنس هندسی اولین ثابت pg = P 1 از دنباله ای از متغیرهای P n به نام plurigenera است .

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

      در مورد انواع پیچیده، (محل های پیچیده) منحنی های غیر منفرد سطوح ریمان هستند . تعریف جبری جنس با مفهوم توپولوژیکی مطابقت دارد . در یک منحنی غیر منحنی، دسته خط متعارف دارای درجه 2 g -2 است .

      مفهوم جنس در بیان قضیه ریمان-روخ (همچنین برای منحنی های جبری به قضیه ریمان-روخ مراجعه کنید ) و فرمول ریمان-هورویتز برجسته است . بر اساس قضیه ریمان-روخ، یک منحنی صفحه تقلیل ناپذیر با درجه d دارای جنس هندسی است.

      {\displaystyle g={\frac {(d-1)(d-2)}{2}}-s,}

      که در آن s تعداد تکینگی ها است.

      اگر C یک ابرسطح غیرقابل تقلیل (و صاف) در صفحه پرتابی باشد که توسط یک معادله چند جمله‌ای با درجه d بریده شده است ، آنگاه دسته خط نرمال آن نوار پیچشی Serre است. {\displaystyle {\mathcal {O}}} , بنابراین با فرمول الحاقی , بسته خط متعارف C با

      {\displaystyle {\mathcal {K}}_{C}=\left[{\mathcal {K}}_{\mathbb {P} ^{2}}+{\mathcal {O}}(d)\راست ]_{\vert C}={\mathcal {O}}(d-3)_{\vert C}}

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

      تعریف جنس هندسی به طور کلاسیک به منحنی های منفرد C منتقل می شود ، با این حکم که

      pg ( C ) _

      جنس هندسی نرمال سازی C است . یعنی از زمان نقشه برداری

      CC

      دوتایی است ، این تعریف با عدم تغییر دوتایی بسط داده شده است.

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

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

      1. دانیلوف و شوکوروف (1998)، ص. 53

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

      دسته بندی :

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

      جنس (ریاضیات)

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

          (تغییر مسیر از جنس (توپولوژی) )

          سطح جنس-2

          در ریاضیات ، جنس ( جمع : جنس ) معانی متفاوت، اما نزدیک به هم دارد. به طور شهودی، جنس تعداد "سوراخ" یک سطح است . [1] یک کره دارای جنس 0 است، در حالی که یک چنبر دارای جنس 1 است.

          توپولوژی [ ویرایش ]

          سطوح جهت‌پذیر [ ویرایش ]

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

          جنس یک سطح متصل و جهت‌پذیر یک عدد صحیح است که نشان‌دهنده حداکثر تعداد قلمه‌ها در امتداد منحنی‌های ساده بسته غیرمتقاطع بدون قطع ارتباط منیفولد حاصل است . [2] برابر است با تعداد دستگیره های روی آن. متناوبا، می‌توان آن را بر حسب مشخصه اویلر χ ، از طریق رابطه χ = 2-2g برای سطوح بسته تعریف کرد ، جایی که g جنس است. برای سطوح با اجزای مرزی b ، معادله χ = 2 - 2 g - b را می‌خواند . در اصطلاح عامیانه، تعداد «سوراخ‌هایی» است که یک جسم دارد («سوراخ» به معنای سوراخ‌های دونات تفسیر می‌شود؛ یک کره توخالی به این معنا دارای سوراخ صفر در نظر گرفته می‌شود). یک چنبر دارای 1 سوراخ است، در حالی که یک کره دارای 0 است. سطح سبز تصویر بالا دارای 2 سوراخ از نوع مربوطه است.

          برای مثال:

          • کره S 2 و یک دیسک هر دو دارای جنس صفر هستند.
          • چنبره دارای جنس یک است، مانند سطح لیوان قهوه با دسته. این منبع شوخی است که "توپولوژیست ها افرادی هستند که نمی توانند دونات خود را از لیوان قهوه خود تشخیص دهند."

          ساخت صریح سطوح از جنس g در مقاله در مورد چندضلعی اساسی آورده شده است .

          به عبارت ساده تر، مقدار جنس یک سطح جهت پذیر برابر با تعداد "سوراخ" است. [3]

          سطوح غیر قابل جهت گیری [ ویرایش ]

          جنس غیر جهت‌پذیر ، demigenus ، یا جنس اویلر از یک سطح بسته متصل و غیرقابل جهت‌گیری ، یک عدد صحیح مثبت است که تعداد کلاهک‌های متقاطع متصل به یک کره را نشان می‌دهد . متناوبا، می‌توان آن را برای یک سطح بسته بر حسب مشخصه χ اویلر، از طریق رابطه χ = 2- k تعریف کرد ، که در آن k جنس غیر قابل جهت‌گیری است.

          برای مثال:

          گره [ ویرایش ]

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

          هندل بادی [ ویرایش ]

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

          برای مثال:

          • یک توپ دارای جنس 0 است.
          • یک چنبره جامد D 2 × S 1 دارای جنس 1 است.

          نظریه گراف [ ویرایش ]

          مقاله اصلی: جاسازی نمودار

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

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

          جنس اویلر حداقل عدد صحیح n است به طوری که نمودار را می توان بدون عبور از خود روی کره ای با n کلاهک متقاطع یا روی کره ای با n/2 دسته رسم کرد. [5]

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

          مشکل جنس گراف NP -complete است . [6]

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

          دو تعریف مرتبط از جنس هر طرح جبری تصویری X وجود دارد : جنس حسابی و جنس هندسی . [7] وقتی X یک منحنی جبری با میدان تعریف اعداد مختلط است ، و اگر X هیچ نقطه مفرد نداشته باشد ، این تعاریف با تعریف توپولوژیکی اعمال شده در سطح ریمان X ( منیفولد نقاط مختلط آن) مطابقت دارند و منطبق هستند. به عنوان مثال، تعریف منحنی بیضوی از هندسه جبری به منحنی تصویری غیر مفرد از جنس 1 با یک نقطه منطقی معین روی آن متصل است .

          توسط قضیه ریمان-روخ ، یک منحنی صفحه تقلیل‌ناپذیر درجهدتوسط مکان ناپدید شدن یک بخش داده می شود{\displaystyle s\in \Gamma (\mathbb {P} ^{2},{\mathcal {O}}_{\mathbb {P} ^{2}}(d))}دارای جنس هندسی

          {\displaystyle g={\frac {(d-1)(d-2)}{2}}-s,}

          جایی کهستعداد تکینگی ها در صورت شمارش صحیح است.

          هندسه دیفرانسیل [ ویرایش ]

          در هندسه دیفرانسیل، یک سرده منیفولد گراممممکن است به عنوان یک عدد مختلط تعریف شود\ Phi (M)مشروط به شرایط

          به عبارت دیگر،\ فیهممورفیسم حلقه است {\displaystyle R\to \mathbb {C} }، جایی کهآرحلقه همدلی گرا تام است. [8]

          جنس\ فیبرای همه دسته‌ها روی منیفولدهای اسپینور با ساختار فشرده متصل ضرب استورود به سیستم{\displaystyle \log _{\Phi }}یک انتگرال بیضوی است مانندورود به سیستم{\displaystyle \log _{\Phi }(x)=\int _{0}^{x}(1-2\delta t^{2}+\varepsilon t^{4})^{-1/2 }dt}برای برخی{\displaystyle \delta,\varepsilon \in \mathbb {C}.}این تیره را تیره بیضوی می نامند.

          ویژگی اویلر\چی (M)از این نظر یک جنس نیست، زیرا در مورد همدلی ها ثابت نیست.

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

          جنس را می توان برای نموداری که توسط خالص فعل و انفعالات شیمیایی در اسیدهای نوکلئیک یا پروتئین ها پوشانده شده است محاسبه کرد. به طور خاص، می توان رشد جنس را در طول زنجیره مطالعه کرد. چنین تابعی (به نام رد جنس) پیچیدگی توپولوژیکی و ساختار حوزه زیست مولکول ها را نشان می دهد. [9]

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

          نقل قول ها [ ویرایش ]

          1. Popescu-Pampu 2016 ، ص. xiii، مقدمه.
          2. Munkres، James R. Topology. جلد 2. رودخانه زین بالایی: پرنتیس هال، 2000.
          3. وایستاین، EW "جنس" . دنیای ریاضی . بازبینی شده در 4 ژوئن 2021 .
          4. آدامز، کالین (2004)، کتاب گره: مقدمه ای ابتدایی بر نظریه ریاضی گره ها ، انجمن ریاضی آمریکا ، ISBN 978-0-8218-3678-1
          5. ^ نمودار روی سطوح .
          6. توماسن، کارستن (1989). "مسئله جنس نمودار NP-complete است". مجله الگوریتم ها . 10 (4): 568-576. doi : 10.1016/0196-6774(89)90006-0 . ISSN 0196-6774 . Zbl 0689.68071 .
          7. هیرزبروک، فردریش (1995) [1978]. روشهای توپولوژیکی در هندسه جبری . کلاسیک در ریاضیات. ترجمه از آلمانی و پیوست یک توسط RLE Schwarzenberger. ضمیمه دو توسط A. Borel (تجدید چاپ دوم، چاپ تصحیح شده از ویرایش سوم). برلین: Springer-Verlag . شابک 978-3-540-58663-0. Zbl 0843.14009 .
          8. چارلز رزک - هم‌شناسی بیضوی و منحنی‌های بیضوی (سخنرانی‌های فلیکس کلین، بن 2015. گروه ریاضیات، دانشگاه ایلینوی، اوربانا، IL)
          9. ^ سولکوفسکی، پیوتر؛ سولکوفسکا، جوانا آی. دابروفسکی-تومانسکی، پاول؛ اندرسن، ابه تنبل؛ جیری، کودی؛ Zając، Sebastian (2018-12-03). "ردیابی جنس پیچیدگی توپولوژیکی و ساختار دامنه زیست مولکول ها را نشان می دهد . " گزارش های علمی 8 (1): 17537. Bibcode : 2018NatSR...817537Z . doi : 10.1038/s41598-018-35557-3 . ISSN 2045-2322 . PMC 6277428 . PMID 30510290 .

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

          نماد ابهام‌زدایی

          این مقاله شامل فهرستی از موارد مرتبط است که نام یکسانی دارند (یا نام‌های مشابه).
          اگر یک پیوند داخلی به اشتباه شما را به اینجا رساند، ممکن است بخواهید پیوند را تغییر دهید تا مستقیماً به مقاله مورد نظر اشاره کند.

          دسته بندی ها :

          https://en.wikipedia.org/wiki/Genus_(mathematics)

          گراف هیوود

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

                نمودار هیوود
                به نامپرسی جان هیوود
                رگه ها14
                لبه ها21
                شعاع3
                قطر3
                بند6
                اتومورفیسم ها336 ( PGL 2 (7) )
                عدد کروماتیک2
                شاخص رنگی3
                جنس1
                ضخامت کتاب3
                شماره صف2
                خواصقفس
                مکعبی دو قسمتی فاصله-گذرا فاصله-منظم حلقوی همیلتونی متقارن شرقی ساده






                جدول نمودارها و پارامترها

                در زمینه ریاضی نظریه گراف ، گراف هیوود یک گراف بدون جهت با 14 راس و 21 یال است که به نام پرسی جان هیوود نامگذاری شده است . [1]

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

                نمودار مکعبی است و تمام چرخه های نمودار دارای شش یا بیشتر یال هستند. هر نمودار مکعبی کوچک‌تر چرخه‌های کوتاه‌تری دارد، بنابراین این نمودار قفس 6 ، کوچک‌ترین نمودار مکعبی دور 6 است. این یک نمودار گذرای فاصله است (به سرشماری فاستر مراجعه کنید ) و بنابراین فاصله منظم است . [2]

                24 تطابق کامل در نمودار هیوود وجود دارد . برای هر تطابق، مجموعه یال‌هایی که مطابقت ندارند، یک چرخه همیلتونی را تشکیل می‌دهند . به عنوان مثال، شکل، رئوس نمودار را نشان می دهد که روی یک چرخه قرار گرفته است، با قطرهای داخلی چرخه که یک تطابق را تشکیل می دهند. با تقسیم لبه‌های چرخه به دو تطابق، می‌توانیم نمودار هیوود را به سه تطابق کامل (یعنی 3 رنگ کردن لبه‌های آن ) به هشت روش مختلف تقسیم کنیم. [2] هر دو تطابق کامل، و هر دو چرخه همیلتونی، می‌توانند توسط یک تقارن نمودار به یکدیگر تبدیل شوند. [3]

                28 چرخه شش رأسی در نمودار هیوود وجود دارد. هر 6 چرخه دقیقاً از سه 6 چرخه دیگر جدا است. در بین این سه 6 چرخه، هر یک تفاوت متقارن دو چرخه دیگر است. نمودار با یک گره در هر 6 چرخه، و یک یال برای هر جفت مجزا از 6 چرخه، نمودار Coxeter است . [4]

                خواص هندسی و توپولوژیکی [ ویرایش ]

                نمودار هیوود یک گراف حلقوی است . یعنی می توان آن را بدون عبور از روی چنبره جاسازی کرد . یک تعبیه از این نوع، رئوس و لبه های خود را در فضای اقلیدسی سه بعدی به عنوان مجموعه رئوس و لبه های یک چندوجهی غیر محدب با توپولوژی یک چنبره، چند وجهی Szilassi قرار می دهد . تعبیه دیگر موارد زیر است: هواپیما را با استفاده از شش ضلعی معمولی کاشی کنید و آنها را به صورت دوره ای با 7 رنگ رنگ کنید. برای هر رنگی، شش ضلعی های این رنگ یک شبکه مثلثی تشکیل می دهند. در این شبکه می توان متوازی الاضلاع را با مرکز در وسط شش ضلعی های رنگ انتخابی گرفت. با تا کردن این متوازی الاضلاع، با استفاده از نمودار هیوود (مانند تصویر در گالری زیر، اما با مربع) یک چنبره با 7 شش ضلعی کاشی‌کاری شده است.

                این نمودار از نام پرسی جان هیوود نامگذاری شده است که در سال 1890 ثابت کرد که در هر تقسیم بندی چنبره به چند ضلعی، مناطق چند ضلعی را می توان حداکثر با هفت رنگ رنگ آمیزی کرد. [5] [6] نمودار هیوود یک بخش فرعی از چنبره را با هفت ناحیه مجاور متقابل تشکیل می‌دهد که نشان می‌دهد این کران تنگ است.

                صفحه فانو و دو نمایش گراف لوی آن (در زیر به عنوان یک گراف دو بخشی )

                گراف هیوود، نمودار لوی صفحه فانو است ، نموداری که نمایانگر انقباضات بین نقاط و خطوط در آن هندسه است. با این تفسیر، 6 چرخه در نمودار هیوود با مثلث های صفحه فانو مطابقت دارد. همچنین، نمودار هیوود، ساختمان Tits از گروه SL 3 (F 2 ) است .

                نمودار هیوود دارای شماره تقاطع 3 است و کوچکترین نمودار مکعبی با آن عدد متقاطع است (توالی A110507 در OEIS ). با احتساب نمودار هیوود، 8 نمودار مجزا از مرتبه 14 با شماره تقاطع 3 وجود دارد.

                نمودار هیوود کوچکترین نمودار مکعبی با گراف کالین دو وردیر ثابت μ = 6 است . [7]

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

                ویژگی های جبری [ ویرایش ]

                گروه اتومورفیسم گراف هیوود به گروه خطی پرتابی PGL 2 (7)، یک گروه از مرتبه 336 هم شکل است. بنابراین، نمودار هیوود یک نمودار متقارن است . دارای اتومورفیسم هایی است که هر راس را به هر راس دیگری و هر یال را به هر یال دیگری می برد. به‌طور قوی‌تر، نمودار هیوود 4 قوس متعدی است . [10] طبق سرشماری فاستر ، نمودار هیوود، که به عنوان F014A ارجاع شده است، تنها نمودار متقارن مکعبی در 14 راس است. [11] [12]

                دارای ضخامت کتاب 3 و صف شماره 2 است . [13]

                چند جمله ای مشخصه نمودار هیوود است(ایکس-3)(ایکس+3)(ایکس2-2)6{\displaystyle (x-3)(x+3)(x^{2}-2)^{6}}. این تنها نمودار با این چند جمله ای مشخص است که آن را به نموداری تبدیل می کند که توسط طیف آن تعیین می شود.

                گالری [ ویرایش ]

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

                1. وایستاین، اریک دبلیو. "Heawood Graph" . دنیای ریاضی .
                2. ^ a bپرش به بالا: Brouwer, Andries E. "Heawood graph" . اضافات و اصلاحات کتاب نمودارهای فاصله-منظم (بروور، کوهن، نویمایر؛ اسپرینگر؛ 1989)
                3. ^ آبرو، م. آلدرد، REL; فانک، ام. جکسون، بیل؛ لبات، دی. Sheehan, J. (2004)، "نمودارها و نمودارها با همه 2 عامل ایزومورفیک"، مجله نظریه ترکیبی، سری B ، 92 (2): 395-404، doi : 10.1016/j.jctb.2004.09.004 ، M. 2099150 .
                4. ↑ Dejter، Italo J. (2011) ، "From the Coxeter graph to the Klein graph"، Journal of Graph Theory ، 70 : 1–9، arXiv : 1002.1960 ، doi : 10.1002/jgt.20597 ، S44ID81 . .
                5. براون، ازرا (2002). "اسامی متعدد از (7،3،1)" (PDF) . مجله ریاضی . 75 (2): 83-94. doi : 10.2307/3219140 . JSTOR 3219140 . بایگانی شده از نسخه اصلی (PDF) در 2012-02-05 . بازیابی 2006-10-27 .
                6. ^ هیوود، پی جی (1890). "قضیه های رنگ آمیزی نقشه". فصلنامه ریاضی . سری اول. 24 : 322-339.
                7. هاین وان در هولست (2006). "نمودارها و موانع در چهار بعد" (PDF) . مجله تئوری ترکیبی، سری B. 96 (3): 388-404. doi : 10.1016/j.jctb.2005.09.004 .
                8. گربراخت، ابرهارد اچ.-آ. (2009). "یازده واحد تعبیه فاصله گراف هیوود". arXiv : 0912.5395 . Bibcode : 2009arXiv0912.5395G . {{cite journal}}: مجله استناد نیاز به |journal=( کمک ) دارد .
                9. ^ باندی، جی . مورتی، ایالات متحده آمریکا (1976). نظریه گراف با کاربردها نیویورک: هلند شمالی. پ. 237 . شابک 0-444-19451-7. بایگانی شده از نسخه اصلی در 2010-04-13 . بازیابی شده 2019-12-18 .
                10. ^ کاندر، مارستون؛ مورتون، مارگارت (1995). "طبقه بندی نمودارهای متقارن سه ظرفیتی مرتبه کوچک" (PDF) . مجله ترکیبیات استرالیایی . 11 : 146.
                11. رویل، جی. "نمودارهای متقارن مکعبی (سرشماری فاستر)." بایگانی شده در 2008-07-20 در Wayback Machine
                12. Conder, M. and Dobcsányi, P. "نمودارهای متقارن سه ظرفیتی تا ۷۶۸ راس." جی. ترکیب. ریاضی. ترکیب کنید. محاسبه کنید. 40، 41-63، 2002.
                13. ^ جسیکا وولز، مهندسی طرح‌بندی‌های خطی با SAT . پایان نامه کارشناسی ارشد، دانشگاه توبینگن، 2018

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

                نمودار حلقوی

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

                یک نمودار مکعبی با 14 راس که روی یک چنبره تعبیه شده است

                نمودار هیوود و نقشه مربوطه در چنبره تعبیه شده است.

                در زمینه ریاضی نظریه گراف , گراف حلقوی گرافی است که می توان آن را روی چنبره تعبیه کرد . به عبارت دیگر، رئوس و یال‌های گراف را می‌توان روی یک چنبره قرار داد که هیچ یالی قطع نشود، مگر در رأسی که به هر دو تعلق دارد.

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

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

                گراف هیوود ، نمودار کامل K 7 (و از این رو K 5 و K 6 )، گراف پترسن (و از این رو نمودار دو بخشی کامل K 3,3 ، از آنجایی که گراف پترسن شامل زیربخشی از آن است)، یکی از بلانوشا snarks ، [1] و تمام نردبان های موبیوس حلقوی هستند. به طور کلی، هر نموداری با شماره 1 حلقوی است. برخی از نمودارها با اعداد متقاطع بزرگتر نیز حلقوی هستند: برای مثال، نمودار موبیوس-کانتور دارای تلاقی شماره 4 و حلقوی است. [2]

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

                هر گراف حلقوی حداکثر دارای عدد کروماتیک 7 است .

                هر نمودار حلقوی بدون مثلث حداکثر دارای عدد رنگی 4 است. [5]

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

                موانع [ ویرایش ]

                بر اساس قضیه رابرتسون-سیمور ، یک مجموعه محدود H از گراف های غیر حلقوی حداقل وجود دارد ، به طوری که یک گراف حلقوی است اگر و فقط اگر گراف جزئی در H نداشته باشد . یعنی H مجموعه مینورهای ممنوعه را برای نمودارهای حلقوی تشکیل می دهد. مجموعه کامل H مشخص نیست، اما حداقل 17523 نمودار دارد. از طرف دیگر، حداقل 250815 نمودار غیر حلقوی وجود دارد که در ترتیب جزئی توپولوژیکی حداقل هستند . یک گراف حلقوی است اگر و فقط اگر هیچ یک از این نمودارها را به عنوان مینور توپولوژیکی نداشته باشد. [9]

                گالری [ ویرایش ]

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

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

                1. ^ اوربانیچ و همکاران. (2004) .
                2. ماروسیچ و پیسانسکی (2000) .
                3. هیوود (1890) .
                4. چارتراند و ژانگ (2008) .
                5. کرونک و وایت (1972) .
                6. کوکای، نیلسون و شیپوفسکی (2001) .
                7. گورتلر، گوتسمن و ترستون (2006) .
                8. ^ اندو (1997) .
                9. Myrvold & Woodcock (2018) .

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

                دسته بندی ها :

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

                نمودار دایک

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

                      نمودار دایک

                      نمودار دایک

                      به نامدبلیو دایک
                      رگه ها32
                      لبه ها48
                      شعاع5
                      قطر5
                      بند6
                      اتومورفیسم ها192
                      عدد کروماتیک2
                      شاخص رنگی3
                      ضخامت کتاب3
                      شماره صف2
                      خواصنمودار متقارن
                      مکعبی
                      همیلتونی
                      دوبخشی کیلی
                      جدول نمودارها و پارامترها

                      در زمینه ریاضی نظریه گراف ، گراف دایک یک نمودار 3 منظم با 32 راس و 48 یال است که به نام والتر فون دایک نامگذاری شده است . [1] [2]

                      همیلتونی با 120 چرخه همیلتونی متمایز است . دارای عدد کروماتیکشاخص رنگی 3، شعاع 5، قطر 5 و دور 6 است. همچنین یک گراف 3- متصل به رأس و یک گراف 3- متصل به لبه است . دارای ضخامت کتاب 3 و صف شماره 2 است . [3]

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

                      ویژگی های جبری [ ویرایش ]

                      گروه اتومورفیسم گراف دایک گروهی از مرتبه 192 است . بنابراین، نمودار دایک یک نمودار متقارن است . دارای اتومورفیسم هایی است که هر راس را به هر راس دیگری و هر یال را به هر یال دیگری می برد. طبق سرشماری فاستر ، نمودار دایک که به عنوان F32A ارجاع داده شده است، تنها نمودار متقارن مکعبی در 32 راس است. [5]

                      چند جمله ای مشخصه نمودار دایک برابر است {\displaystyle (x-3)(x-1)^{9}(x+1)^{9}(x+3)(x^{2}-5)^{6}}.

                      نقشه دایک [ ویرایش ]

                      نمودار دایک اسکلت یک رگه متقارن سطحی از جنس سه در دوازده هشت ضلعی است که به نقشه دایک یا کاشی کاری دایک معروف است . نمودار دوگانه برای این کاشی کاری، نمودار سه جانبه کامل K 4،4،4 است . [6] [7]

                      گالری [ ویرایش ]

                      • ترسیم جایگزین نمودار دایک.

                        ترسیم جایگزین نمودار دایک.

                      • عدد رنگی نمودار دایک 2 است.

                        عدد رنگی نمودار دایک 2 است.

                      • شاخص رنگی نمودار دایک 3 است.

                        شاخص رنگی نمودار دایک 3 است.

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

                      1. دایک، دبلیو (1881)، «Über Aufstellung und Untersuchung von Gruppe und Irrationalität regulärer Riemann'scher Flächen» ، ریاضی. ان , 17 (4): 473, doi : 10.1007/bf01446929 , S2CID 122956853.
                      2. وایستاین، اریک دبلیو. "دیک گراف" . دنیای ریاضی .
                      3. ^ ولز، جسیکا؛ مهندسی طرح های خطی با SAT. پایان نامه کارشناسی ارشد، دانشگاه توبینگن، 2018
                      4. ^ داده های Royle, G. F032A [ پیوند مرده دائمی ]
                      5. ^ کاندر، ام . Dobcsányi, P. (2002), "گرافهای متقارن سه ظرفیتی تا 768 راس"، J. Combin. ریاضی. ترکیب کنید. محاسبه کنید. ، 40 : 41-63.
                      6. Dyck, W. (1880), "Notiz über eine reguläre Riemannsche Fläche vom Geschlecht 3 und die zugehörige Normalkurve 4. Ordnung" , Math. ان ، 17 : 510–516، doi : 10.1007/bf01446930 ، S2CID 121904710 .
                      7. Ceulemans، A. (2004)، "گروه چهارکیزوکتاهدرال گراف دایک و تحقق مولکولی آن."، فیزیک مولکولی ، 102 (11): 1149-1163، doi : 10.1080/002689704100017 S200017 ، 10.1080/ 002689704100017 .

                      دسته بندی ها :

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

                      نماد LCF

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

                          نمودار نائورو [1] دارای نماد LCF است [5, –9, 7, –7, 9, –5] 4 .

                          در زمینه ریاضی تئوری گراف , نماد LCF یا کد LCF نمادی است که توسط جاشوا لدربرگ ابداع شده و توسط HSM Coxeter و Robert Frucht برای نمایش نمودارهای مکعبی که شامل یک چرخه همیلتونی هستند توسعه یافته است . [2] [3] خود چرخه شامل دو مورد از سه مجاورت برای هر راس است ، و نماد LCF مشخص می‌کند که همسایه سوم هر راس چقدر در طول چرخه است. یک گراف منفرد ممکن است چندین نمایش متفاوت در نماد LCF داشته باشد.

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

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

                          اغلب این الگو تکرار می شود و تعداد تکرارها را می توان با یک بالانویس در نماد نشان داد. به عنوان مثال، نمودار نائورو ، [1] که در سمت راست نشان داده شده است، دارای چهار تکرار از همان شش آفست است و می تواند با نماد LCF نشان داده شود [5, −9, 7, −7, 9, −5] 4 . بسته به انتخاب چرخه هامیلتونی و راس شروع، یک نمودار واحد ممکن است دارای چندین نماد LCF مختلف باشد.

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

                          علامت گذاری LCF در انتشار توضیحات مختصر نمودارهای مکعبی هامیلتونی مانند مثال های زیر مفید است. علاوه بر این، برخی از بسته‌های نرم‌افزاری برای دستکاری نمودارها شامل ابزارهایی برای ایجاد یک نمودار از نماد LCF هستند. [5]

                          اگر یک نمودار با نماد LCF نشان داده شود، آزمایش دوبخشی بودن نمودار ساده است : این درست است اگر و تنها در صورتی که همه جابجایی ها در نماد LCF فرد باشند. [6]

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

                          نامرگه هانماد LCF
                          نمودار چهار وجهی4[2] 4
                          نمودار سودمند6[3] 6
                          نمودار مکعبی8[3،-3] 4
                          نمودار واگنر8[4] 8 یا [4،-3،3،4] 2
                          مکعب بیدیاکیس12[6،4،-4] 4 یا [6،-3،3،6،3،-3] 2 یا [-3،6،4،-4،6،3، -4،6،-3، 3،6،4]
                          نمودار فرانکلین12[5،-5] 6 یا [-5،-3،3،5] 3
                          نمودار فروخت12[-5،-2،-4،2،5،-2،2،5،-2،-5،4،2]
                          نمودار چهار وجهی کوتاه شده12[2،6،-2] 4
                          نمودار هیوود14[5،-5] 7
                          نمودار موبیوس-کانتور16[5،-5] 8
                          نمودار پاپوس18[5،7،-7،7،-7،-5] 3
                          کوچکترین نمودار متقارن صفر [7]18[5،-5] 9
                          نمودار Desargues20[5،-5،9،-9] 5
                          نمودار دوازده وجهی20[10،7،4،-4،-7،10،-4،7،-7،4] 2
                          نمودار مک گی24[12،7،-7] 8
                          نمودار مکعبی کوتاه شده24[2،9،-2،2،-9،-2] 4
                          نمودار هشت وجهی کوتاه شده24[3،-7،7،-3] 6
                          نمودار نائورو24[5،-9،7،-7،9،-5] 4
                          نمودار F26A26[-7، 7] 13
                          نمودار Tutte-Coxeter30[-13،-9،7،-7،9،13] 5
                          نمودار دایک32[5،-5،13،-13] 8
                          نمودار خاکستری54[-25،7،-7،13،-13،25] 9
                          نمودار دوازده وجهی کوتاه شده60[30, −2, 2, 21, −2, 2, 12, −2, 2, −12, −2, 2, −21, −2, 2, 30, −2, 2, −12, −2 , 2, 21, −2, 2, −21, −2, 2, 12, −2, 2] 2
                          نمودار هریس705 _
                          نمودار هریس-ونگ70[9، 25، 31، -17، 17، 33، 9، -29، -15، -9، 9، 25، -25، 29، 17، -9، 9، -27، 35، -9، 9 ، −17، 21، 27، −29، −9، −25، 13، 19، −9، −33، −17، 19، −31، 27، 11، −25، 29، −33، 13، − 13، 21، -29، -21، 25، 9، -11، -19، 29، 9، -27، -19، -13، -35، -9، 9، 17، 25، -9، 9، 27، -27، -21، 15، -9، 29، -29، 33، -9، -25]
                          بالابان 10-قفس70[-9، −25، −19، 29، 13، 35، −13، −29، 19، 25، 9، −29، 29، 17، 33، 21، 9،−13، −31، −9، 25، 17، 9، -31، 27، -9، 17، -19، -29، 27، -17، -9، -29، 33، -25،25، -21، 17، -17، 29، 35، −29، 17، −17، 21، −25، 25، −33، 29، 9، 17، −27، 29، 19، −17، 9، −27، 31، −9، −17، − 25، 9، 31، 13، -9، -21، -33، -17، -29، 29]
                          نمودار فاستر90[17،-9،37،-37،9،-17] 15
                          نمودار بیگز-اسمیت102[16، 24، −38، 17، 34، 48، −19، 41، −35، 47، −20، 34، −36، 21، 14، 48، −16، −36، −43، 28، − 17، 21، 29، -43، 46، -24، 28، -38، -14، -50، -45، 21، 8، 27، -21، 20، -37، 39، -34، -44، -8، 38، -21، 25، 15، -34، 18، -28، -41، 36، 8، -29، -21، -48، -28، -20، -47، 14، -8، −15، −27، 38، 24، −48، −18، 25، 38، 31، −25، 24، −46، −14، 28، 11، 21، 35، −39، 43، 36، −38 ، 14، 50، 43، 36، -11، -36، -24، 45، 8، 19، -25، 38، 20، -24، -14، -21، -8، 44، -31، -38 ، −28، 37]
                          بالابان 11-قفس112[44، 26، -47، -15، 35، -39، 11، -27، 38، -37، 43، 14، 28، 51، -29، -16، 41، -11، -26، 15، 22، -51، -35، 36، 52، -14، -33، -26، -46، 52، 26، 16، 43، 33، -15، 17، -53، 23، -42، -35، −28، 30، −22، 45، −44، 16، −38، −16، 50، −55، 20، 28، −17، −43، 47، 34، −26، −41، 11، −36 ، −23، −16، 41، 17، −51، 26، −33، 47، 17، −11، −20، −30، 21، 29، 36، −43، −52، 10، 39، −28 ، −17، −52، 51، 26، 37، −17، 10، −10، −45، −34، 17، −26، 27، −21، 46، 53، −10، 29، −50، 35 ، 15، -47، -29، -41، 26، 33، 55، -17، 42، -26، -36، 16]
                          نمودار لیوبلیانا112[47، -23، -31، 39، 25، -21، -31، -41، 25، 15، 29، -41، -19، 15، -49، 33، 39، -35، -21، 17 ، −33، 49، 41، 31، −15، −29، 41، 31، −15، −25، 21، 31، −51، −25، 23، 9، −17، 51، 35، −29، 21، -51، -39، 33، -9، -51، 51، -47، -33، 19، 51، -21، 29، 21، -31، -39] 2
                          توت 12 قفس1267 ،

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

                          یک نسخه توسعه یافته پیچیده تر از نماد LCF توسط Coxeter، Frucht و Powers در کارهای بعدی ارائه شد. [8] به ویژه، آنها یک نماد "ضد پالیندرومیک" معرفی کردند: اگر نیمه دوم اعداد بین پرانتزهای مربع معکوس نیمه اول بود، اما با تغییر همه علائم، آنگاه با یک نقطه ویرگول و جایگزین می شد. یک خط تیره. نمودار نائورو این شرط را با [5, −9, 7, −7, 9, −5] 4 برآورده می‌کند و بنابراین می‌توان نوشت [5, −9, 7; −] 4 در نماد توسعه یافته. [9]

                          منبع

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

                          گراف کاکستر

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

                          این مقاله در مورد گراف 3 منظم است. برای گراف مرتبط با یک گروه کوکستر، گراف کوکستر را ببینید .

                          نباید با گراف توت-کوکستر اشتباه گرفته شود .

                          گراف کاکستر

                          گراف کوکستر

                          به نامHSM کوکستر

                          رگه ها28

                          لبه ها42

                          شعاع4

                          قطر4

                          بند7

                          اتومورفیسم ها336 ( PGL 2 (7))

                          عدد کروماتیک3

                          شاخص رنگی3

                          ضخامت کتاب3

                          شماره صف2

                          خواصفاصله متقارن
                          -
                          فاصله منظم-مکعب
                          هیپوهامیلتونین
                          متعدی

                          جدول گرافها و پارامترها

                          در زمینه ریاضی نظریه گراف ، گراف کاکستر یک گراف 3 منظم با 28 راس و 42 یال است. [1] این یکی از 13 گراف منتظم فاصله مکعبی شناخته شده است . [2] این نام از هارولد اسکات مک دونالد کاکستر گرفته شده است .

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

                          گراف کوکستر دارای عدد کروماتیک 3، شاخص رنگی 3، شعاع 4، قطر 4 و دور 7 است. همچنین یک گراف 3-متصل به رأس و یک گراف متصل به لبه است . دارای ضخامت کتاب 3 و صف شماره 2 است . [3]

                          گراف کاکستر هیپوهامیلتونی است : خود چرخه همیلتونی ندارد اما هر گرافی که با حذف یک رأس از آن شکل می‌گیرد، همیلتونی است. دارای شماره تقاطع مستطیلی 11 است و کوچکترین گراف مکعبی با آن عدد تلاقی [4] است (توالی A110507 در OEIS ).

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

                          ساده ترین ساخت گراف کاکستر از هواپیمای فانو است . 7 C 3 = 35 3 ترکیب ممکن روی 7 شی را در نظر بگیرید . 7 سه قلو که مطابق با خطوط هواپیمای فانو هستند را دور بیندازید و 28 سه قلو باقی بمانید. اگر دو سه قلو ناهمگون هستند پیوند دهید. نتیجه گراف کوکستر است. ( تصویر را ببینید .) این ساختار گراف کوکستر را به عنوان یک زیرگراف القایی از گراف فرد O 4 نشان می دهد که به عنوان گراف Kneser KG 7,3 نیز شناخته می شود .

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

                          گراف کوکستر ممکن است از گراف هافمن-سینگلتون مشتق شده باشد . هر رأس v را در گراف هافمن-سینگلتون در نظر بگیرید. یک مجموعه مستقل از سایز 15 وجود دارد که شامل v . 7 همسایه v و کل مجموعه مستقل از جمله v را حذف کنید و گراف کوکستر را پشت سر بگذارید.

                          ویژگی های جبری [ ویرایش ]

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

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

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

                          تنها پنج نمونه از گراف رأس گذرا بدون چرخه هامیلتونی شناخته شده است: گراف کامل K2 ، گراف پترسن ، گراف کاکستر و دو گراف مشتق شده از گرافهای پترسن و کاکستر با جایگزینی هر راس با یک مثلث . [9]

                          چند جمله ای مشخصه گراف کاکستر است(x-3)(x-2)^{8}(x+1)^{7}(x^{2}+2x-1)^{6}. این تنها گراف با این چند جمله ای مشخص است که آن را به گرافی تبدیل می کند که توسط طیف آن تعیین می شود.

                          گالری [ ویرایش ]

                          طرح بندی [ ویرایش ]

                          اینها نمایش های متفاوتی از گراف کوکستر با استفاده از برچسب های رأس یکسان هستند. چهار رنگ و هفت رأس هر رنگ وجود دارد.
                          هر رأس قرمز، سبز یا آبی با دو راس همرنگ (لبه های نازک 7 چرخه) و یک راس سفید (لبه های ضخیم) متصل است.

                          هفت ضلعی قرمز ، هپتاگرام حاد سبز و آبی
                          سمت چپ: تقارن چرخشی 7 برابر

                          در 24 گون
                          تقارن چرخشی 3 برابر

                          تقارن دو وجهی 3 برابری
                          ( نوعی را با رئوس صفحه فانو مقایسه کنید )

                          در تقارن آینه هشت ضلعی

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

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

                          عدد رنگی گراف کاکستر 3 است.

                          عدد متقاطع مستطیلی گراف کوکستر 11 است.

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

                          1. وایستاین، اریک دبلیو. "کوکستر Graph" . دنیای ریاضی .
                          2. ^ بروور، AE; کوهن، AM; و Neumaier، A. گرافهای فاصله-منظم. نیویورک: Springer-Verlag، 1989.
                          3. ^ ولز، جسیکا؛ مهندسی طرح های خطی با SAT. پایان نامه کارشناسی ارشد، دانشگاه توبینگن، 2018
                          4. ^ هایتورپ، مایکل؛ نیوکمب، الکس (2018)، هیچ گراف مکعبی روی 26 رأس با شماره 11 وجود ندارد ، arXiv : 1804.10336
                          5. ↑ Dejter، Italo J. (2011) ، "From the کوکستر graph to the Klein graph"، Journal of Graph Theory ، 70 : 1–9، arXiv : 1002.1960 ، doi : 10.1002/jgt.20597 ، S44ID81 . .
                          6. ^ داده های Royle, G. F028A [ پیوند مرده دائمی ]
                          7. Conder, M. and Dobcsányi, P. "گرافهای متقارن سه ظرفیتی تا ۷۶۸ راس." جی. ترکیب. ریاضی. ترکیب کنید. محاسبه کنید. 40، 41-63، 2002.
                          8. ER van Dam و WH Haemers، خصوصیات طیفی برخی از گرافهای منظم فاصله. ج. ترکیب جبری. 15، صفحات 189-202، 2003
                          9. رویل، جی. "گرافهای متقارن مکعبی (سرشماری فاستر)." بایگانی شده در 12-09-2015 در ماشین Wayback
                          • کوکستر، HSM "گراف i." Proc. ریاضی لندن. Soc. 46، 117-136، 1983.

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

                          2-ایزومورفیسم گراف

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

                          • "برچسب گذاری متعارف نمودار" توسط لازلو بابای و یوجین ام. لوکس STOC 1983 

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

                          • نمودارهای مسطح: "الگوریتم زمان خطی برای هم ریختی نمودارهای مسطح" توسط JE Hopcroft و JK Wong، STOC 1974 ( مقاله در اینجا )
                          • یا به طور کلی نمودارهای جنس محدود: "آزمایش ایزومورفیسم برای نمودارهای جنس محدود" توسط گری میلر، STOC 1980 ( مقاله در اینجا )
                          • نمودارها با درجه محدود: "ایزومورفیسم نمودارهای ظرفیت محدود را می توان در زمان چند جمله ای آزمایش کرد" توسط یوجین ام. لوکس، مجله علوم کامپیوتر و سیستم 25: 42-65، 1982 ( مقاله در اینجا )

                          در امتداد یک رگه مشابه، یک الگوریتم زمانی زیر نمایی برای نمودارهای به شدت منظم وجود دارد که بهتر از بهترین الگوریتم کلی است که در بالا توضیح داده شد:

                          • "تست سریعتر ایزومورفیسم نمودارهای با قاعده قوی" توسط Daniel A. Spielman STOC 1996 (مقاله در اینجا)

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

                          • «الگوریتم‌های نظری گروهی و ایزومورفیسم نمودار» توسط CM Hoffman 1982 

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

                          • "مسئله ایزومورفیسم گراف: پیچیدگی ساختاری آن" توسط یوهانس کوبلر، اووه شونینگ، یاکوبو توران (1993) 

                          که در آن شما برخی از نتایج خوب نظریه پیچیدگی پایه را در مورد ایزومورفیسم گراف پیدا خواهید کرد.
                          خوب حالا که رفته اید و شروع به یادگیری در مورد برخی پیچیدگی های محاسباتی در رابطه با هم ریختی گراف کرده اید، احتمالا زمان خوبی برای توقف و بررسی الگوریتم های عملی واقعی برای ایزومورفیسم گراف است. پادشاه تپه اینجا، تا جایی که من می دانم، برنامه ناوتی (بدون AUTomorphism، بله؟) توسط برندان دی. مک کی است. متأسفانه به نظر می رسد که یک موتور جستجوی خاص نسبت به کلمه "شیطان" کمی سنگین است (توجه داشته باشید، هنگام نامگذاری یک بسته نرم افزاری، کلمه کلیدی مرتبط با پورن را در نظر بگیرید):

                          وظیفه اصلی Nauty تعیین گروه اتومورفیسم یک گراف (گروهی از جایگشت‌ها که نمایش گراف را بدون تغییر می‌گذارند) است، اما nauty یک برچسب متعارف نیز تولید می‌کند که می‌تواند برای آزمایش هم‌شکلی استفاده شود. Nauty می تواند تست های هم ریختی نمودارهای 100 راس را در حدود یک ثانیه انجام دهد. مقاله ضمیمه ای وجود دارد که نحوه عملکرد ناوتی را توضیح می دهد:

                          • "ایزومورفیسم نمودار عملی"، توسط برندان دی. مک کی، کنگره Numerantium، 30، 45-87، 1981. 

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

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

                          منبع

                          https://dabacon.org/pontiff/2010/08/04/reading-list-graph-isomorphism/

                          1-ایزومورفیسم گراف


                          ارسال شده در 4 آگوست 2010 توسط dabacon

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

                          مسئله ایزومورفیسم گراف یک مسئله جالب است. گراف مجموعه ای از رئوس به همراه یال هایی است که این رئوس را به هم متصل می کنند. مسئله ایزومورفیسم گراف این است که با توجه به توصیف دو نمودار، تعیین کنیم که آیا این توصیفات واقعاً همان نمودار هستند یا خیر. به عنوان مثال، آیا می توان رئوس دو نمودار زیر را مجدداً برچسب زد و جابه جا کرد تا یکسان به نظر برسند؟

                          دست برداشتن از؟ خوب، خوب این یکی خیلی سخت نبود، اما بله، این نمودارها هم شکل هستند 🙂معمولاً دو تصویر از نمودارها به ما داده نمی شود، اما در عوض توضیح مختصری از این که چه رئوسی به یکدیگر متصل هستند، داده می شود. این توسط یا و ماتریس مجاورت یا و لیست مجاورت داده می شود. ماتریس مجاورت یک نمودار بارئوس است ماتریس که ورودی دهم تعداد یال های راس استبه. یک الگوریتم برای مسئله ایزومورفیسم گراف کارآمد است اگر زمان اجرای آن چند جمله ای در تعداد رئوس نمودارهای درگیر باشد.
                          یکی از دلایل جالب توجه هم ریختی گراف، وضعیت فعلی آن در پیچیدگی محاسباتی است. به احتمال زیاد NP-کامل نیست (زیرا این امر باعث فروپاشی سلسله مراتب چند جمله‌ای می‌شود)، اما با وجود مقدار قابل توجهی کار، هیچ الگوریتم زمان چند جمله‌ای شناخته‌شده‌ای برای این مشکل وجود ندارد. مشخص شده است که ایزومورفیسم نمودار در کلاس پیچیدگی NP intersect co-AM است، که به نوعی شبیه به جایی است که نسخه تصمیم گیری فاکتورگیری در آن قرار دارد (NP intersect co-NP.) این شباهت، همراه با این واقعیت که تعمیم طبیعی حل مسئله کوانتومی با فاکتورگیری ( مسئله زیرگروه پنهان) مربوط به ایزومورفیسم گراف است (حل کارآمد مسئله زیرگروه پنهان برای گروه متقارن، الگوریتم کارآمدی را برای ایزومورفیسم گراف به دست می دهد) به این امید منجر شده است که رایانه های کوانتومی ممکن است بتوانند به طور کارآمد ایزومورفیسم گراف را حل کنند. اعتراف می‌کنم که طی سال‌ها، من به آرامی اما مطمئناً به بیماری هم‌شکلی گراف کاملاً شدید مبتلا شده‌ام، اگرچه به نظر می‌رسد که مورد من از نوع کوانتومی است. مانند هر بیماری، گسترش بیماری مهم است. بنابراین در اینجا مجموعه ای از خواندنی ها در مورد مسئله ایزورموفیسم گراف ارائه شده است.
                          یکی از جنبه‌های جالب مسئله ایزومورفیسم گراف این است که کلاس‌هایی از نمودارها وجود دارند که الگوریتم‌های زمانی چند جمله‌ای کارآمدی برای تعیین هم‌شکل گراف‌ها در این کلاس‌ها وجود دارند. از آنجایی که می‌توان خیلی سریع سر خود را در برابر مشکل شکست داد، فکر می‌کنم خوب است که با یک مورد ساده شروع کنیم: هم‌شکل درختی. الگوریتم کارآمد برای این معمولا به آهو، هاپکرافت و اولمن (1974) نسبت داده می شود، اما من واقعا دوست دارم

                          • «الگوریتم‌های ایزومورفیسم درختی: سرعت در مقابل وضوح» توسط داگلاس ام. کمپبل و دیوید رادفورد ، مجله ریاضیات ، جلد. 64، شماره 4 (مهر، 1991)، صفحات 252-261

                          مطمئنم این یک خواندن آسان و سرگرم کننده است که همه شما را در مورد ایزومورفیسم گراف هیجان زده می کند.
                          خوب پس از آن شروع سرگرم کننده، شاید ماندن در قلمرو الگوریتم های زمانی چند جمله ای همچنان احساس خوبی داشته باشد. یکی از روش‌های کلاسیک برای حل هم‌شکلی گراف به شرح زیر است: مقادیر ویژه ماتریس‌های مجاورت دو نمودار را محاسبه کنید و این مقادیر ویژه را مرتب کنید. اگر مقادیر ویژه متفاوت باشند، نمودارها نمی توانند هم شکل باشند. چرا؟ خوب اگر نمودارها هم شکل باشند، a وجود داردماتریس جایگشت(ماتریسی ساخته شده از صفر و یک که در هر سطر و هر ستون فقط یک عدد دارد) به طوری که و به یاد بیاورید که مقادیر ویژه وبرای ماتریس های معکوس یکسان هستند. بنابراین نمودارهای هم شکل باید مقادیر ویژه یکسانی داشته باشند. البته توجه داشته باشید که این بدان معنا نیست که نمودارهای غیر هم شکل دارای مقادیر ویژه متفاوتی هستند.  از طرف دیگر، اگر مقادیر ویژه ماتریس های مجاورت آنها را بگیرید، متوجه خواهید شد که هر دوی آنها توسط

                          بنابراین نمودارهای هم‌طیفی (همان مقادیر ویژه ماتریس مجاورت) اما غیر هم شکل وجود دارد. بنابراین گرفتن مقادیر ویژه نمودار برای تشخیص گراف غیر هم شکل کافی نیست. با این حال، در عمل، این معمولاً بسیار خوب عمل می کند. بعلاوه، اگر نمودارهایی را در نظر بگیریم که در آنها حداکثر تعدد مقادیر ویژه (به یاد بیاورید که یک مقدار ویژه ممکن است چندین بار در لیست مقادیر ویژه یک ماتریس ظاهر شود - تعدد تعداد دفعاتی است که یک مقدار ویژه ظاهر می شود) محدود است (یعنی تعدد وجود دارد. با اندازه گراف رشد نمی کند)، پس یک الگوریتم کارآمد برای ایزومورفیسم گراف وجود دارد. این اولین بار برای نمودارهای تعدد یک، یعنی جایی که همه مقادیر ویژه متمایز هستند، توسط لیتون و میلر نشان داده شد. این اثر منتشر نشده است، اما می توانید یادداشت های دست نوشته را در وب سایت گری میلر بیابید:

                          • «گواهینامه‌هایی برای نمودارها با مقادیر ویژه مشخص» توسط F. Thomson Leighton و Gary l. میلر، منتشر نشده، 1979 

                          مکان دیگری برای یادگیری در مورد این، بدون تمام علائم لک، در سایت دوره ییل دان اسپیلمن است:

                          در اینجا مکان خوبی برای ذکر حالت کلی برای تعدد محدود است

                          • "ایزومورفیسم نمودارها با کثرت مقدار ویژه محدود" توسط لازلو بابای، دی. یو. گریگوریف و دیوید ام مونت، STOC 1982 

                          منبع

                          https://dabacon.org/pontiff/2010/08/04/reading-list-graph-isomorphism/

                          تعیین مقادیر ویژه و بردارهای ویژه   ماتریس 3×3

                          مقادیر ویژه و بردارهای ویژه 3×3 مثال ماتریس

                          وظیفه:

                          بردارهای ویژه و مقادیر ویژه ماتریس زیر را بیابید:

                           

                          راه حل:

                          برای یافتن بردارهای ویژه باید معادله زیر را برای هر مقدار ویژه حل کنیم:

                          مقادیر ویژه ریشه های معادله مشخصه هستند:

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

                          بردارهای ویژه برای:

                          حال باید معادله زیر را حل کنیم:


                          ابتدا اجازه دهید ماتریس را کاهش دهیم:

                               

                          این به معادله کاهش می یابد:

                          بردارهای ویژه برای:

                          حال باید معادله زیر را حل کنیم:

                          ابتدا اجازه دهید ماتریس را کاهش دهیم:

                           

                          این به معادله کاهش می یابد:

                          منبع

                          https://assignmentshark.com/blog/eigenvalues-and-eigenvectors-of-3x3-matrix-example/

                          تعیین مقادیر ویژه یک ماتریس

                          تعیین مقادیر ویژه یک ماتریس

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

                          با توجه به یک ماتریس مربع A ، شرطی که یک مقدار ویژه، λ را مشخص می کند، وجود یک بردار غیرصفر x است به طوری که

                           x = λ x ; این معادله را می توان به صورت زیر بازنویسی کرد:

                           

                            

                           

                           

                          این شکل نهایی معادله روشن می کند که x حل یک سیستم مربعی و همگن است. اگر راه حل های غیر صفر مورد نظر باشد، آنگاه تعیین کننده ماتریس ضریب - که در این مورد A - λ I است - باید صفر باشد. اگر نه، آنگاه سیستم فقط دارای راه حل بی اهمیت x = 0 است. از آنجایی که بردارهای ویژه، طبق تعریف، غیر صفر هستند، برای اینکه x بردار ویژه ماتریس A باشد ، λ باید طوری انتخاب شود که 

                           

                           

                           

                          هنگامی که دترمینان A - λ I نوشته می شود، عبارت به دست آمده یک چند جمله ای مونیک در λ است. [ چندجمله‌ای مونیک آن است که ضریب جمله پیشرو (بالاترین درجه) 1 باشد.] به آن چند جمله‌ای مشخصه A می‌گویند و اگر nxn باشد درجه n خواهد بود . صفرهای چند جمله‌ای مشخصه A - یعنی جواب‌های معادله مشخصه ، det( A - λ I ) = 0- مقادیر ویژه A هستند.

                          مثال 1 : مقادیر ویژه ماتریس را تعیین کنید

                           

                            

                           

                           

                          ابتدا ماتریس A - λ I را تشکیل دهید : 

                           

                           

                           

                          نتیجه ای که به سادگی با کم کردن λ از هر یک ازدرایه های قطر اصلی به دست می آید. حال، دترمینان  A - λ I را بگیرید :

                           

                           

                           

                          این چند جمله ای مشخصه A است، و جواب های معادله مشخصه، det( A - λ I ) = 0، مقادیر ویژه A هستند :

                           

                            

                           

                           

                          در برخی متون، چند جمله ای مشخصه A به جای det ( A - λ I )مقدار det (λI - A ) نوشته می شود. برای ماتریس های با ابعاد زوج، این چند جمله ای ها دقیقاً یکسان هستند، در حالی که برای ماتریس های مربعی با ابعاد فرد، این چند جمله ای ها معکوس جمعی هستند. این تمایز صرفا جنبه زیبایی دارد، زیرا محلول‌های det (λI - A ) = 0 دقیقاً مشابه محلول‌های det ( A - λ I ) = 0 هستند. بنابراین، چه چند جمله‌ای مشخصه A را به عنوان det بنویسید. λ I − A ) یا به صورت det( A − λ I) هیچ تأثیری در تعیین مقادیر ویژه یا بردارهای ویژه مربوط به آنها نخواهد داشت.

                          مثال 2 : مقادیر ویژه ماتریس 3 در 3 شطرنجی را بیابید

                           

                            

                           

                          دترمینان 

                           

                             

                           

                          ابتدا ردیف دوم را به ردیف سوم اضافه می کنیم و سپس یک بسط لاپلاس توسط ستون اول انجام می دهیم:

                           

                           

                           

                          ریشه های معادله مشخصه،

                          -λ^ 2 (λ - 3) = 0، λ = 0 و λ = 3

                          هستند. اینها مقادیر ویژه C هستند.

                          منبع

                          https://www.cliffsnotes.com/study-guides/algebra/linear-algebra/eigenvalues-and-eigenvectors/determining-the-eigenvalues-of-a-matrix

                          1-مثال از تعیین چند جمله ای مشخصه و مقادیر ویژه یک ماتریس 2 در 2

                          MATLAB Eigenvalues and Eigenvectors - Javatpoint

                          گراف دیک

                           

                          گراف دیک
                          گراف دیک hamiltonian.svg

                          گراف دیک

                          به نامد. دیک
                          رگه ها32
                          لبه ها48
                          شعاع5
                          قطر5
                          تولد6
                          خودشکلی ها192
                          شماره رنگی2
                          شاخص رنگی3
                          ضخامت کتاب3
                          شماره صف2
                          خواصگراف متقارن
                          مکعبی
                          Hamiltonian
                          دو طرفه
                          Cayley
                          جدول گرافها و پارامترها

                          در زمینه ریاضی نظریه گراف ، گراف دیک یک گراف 3 ممرتبه با 32 راس و 48 لبه است که به نام والتر ون دایک نامگذاری شده است . [1] [2]

                          این همیلتونی با 120 دور متمایز همیلتونی است. دارای شماره رنگی 2 ، شاخص رنگی 3 ، شعاع 5 ، قطر 5 و دور 6 است. همچنین یک گراف 3 راس متصل و 3 گراف متصل به لبه است . دارای ضخامت کتاب 3 و صف شماره 2 است. [3]

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

                           

                          فهرست

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

                          گروه خودریختی گراف دایک گروهی از مرتبه 192 است. [4] روی رأس ها ، لبه ها و قوس های گراف به صورت گذرا عمل می کند. بنابراین ، گراف دیک یک گراف متقارن است . دارای خودریختی هایی است که هر راس را به هر رأس دیگر و هر لبه را به هر لبه دیگر می رساند. بر اساس سرشماری فاستر ، گراف دیک که با نام F32A شناخته می شود ، تنها گراف متقارن مکعبی در 32 رأس است. [5]

                          چند جمله ای مشخصه از گراف دایک برابر است با(x-3) (x-1)^{9} (x+1)^{9} (x+3) (x^{2} -5)^{6}به

                          نقشه دیک [ ویرایش ]

                          گراف دیک اسکلت یک قرینه شدن متقارن سطح جنس سه در دوازده هشت ضلعی است که به عنوان نقشه دیک یا دیک tiling شناخته می شود . گراف دو برای این کاشی کاری است گراف سه جانبه کامل 4،4،4 . [6] [7]

                          گالری [ ویرایش ]

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

                           

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

                          در نظریه گراف ، این نردبان موبیوس N است مکعب نمودار گردشی با تعداد حتی N از رئوس، تشکیل از N - چرخه با اضافه کردن لبه ها (به نام "پله") اتصال جفت مخالف از رئوس در چرخه است. این نام به این دلیل است که (به استثنای 6 = 3،3 ) n دقیقاً دارای n / 2 4 چرخه است [1] که با لبه های مشترک خود به یکدیگر متصل می شوند و یک نوار توپولوژیک Möbius تشکیل می دهند . نردبان های موبیوس توسط گای نامگذاری و مورد مطالعه قرار گرفتو هاری  ( 1967 ).

                           

                          فهرست

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

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

                          نردبان های Möbius یک راس-انتقالی هستند - آنها دارای تقارن هایی هستند که هر راس را به هر راس دیگر منتقل می کنند - اما (دوباره به استثنای 6 ) لبه های انتقالی نیستند . لبه های چرخه ای که نردبان از آن تشکیل شده است را می توان از ردیف های نردبان تشخیص داد ، زیرا هر لبه چرخه به یک 4 چرخه اختصاص دارد ، در حالی که هر پله به دو چرخه از این دست تعلق دارد. بنابراین ، هیچ قرینه ای وجود ندارد که یک لبه چرخه را به یک لبه پله ای بردارید یا بالعکس.

                          وقتی n ≡ 2 (mod 4) ، n دو بخشی است . وقتی n ≡ 0 باشد (mod 4) ، دو بخشی نیست. نقاط انتهایی هر پله در چرخه ابتدایی فاصله مساوی دارند ، بنابراین افزودن هر پله یک چرخه فرد ایجاد می کند. در این حالت ، از آنجا که نمودار 3 منظم است اما دو بخشی نیست ، با توجه به قضیه بروکس دارای شماره رنگی 3 است. De Mier & Noy (2004) نشان می دهد که نردبان های Möbius به طور منحصر به فرد توسط چند جمله ای Tutte تعیین می شوند .

                          نردبان موبیوس 8 دارای 392 درخت پوشا است . آن و 6 دارای بیشترین درختان پوشا در میان نمودارهای مکعبی با تعداد راس یکسان هستند. [2] با این حال ، نمودار مکعب 10 راس با بیشترین درختان ، نمودار Petersen است ، که یک نردبان موبیوس نیست.

                          چند جمله ای Tutte از نردبان موبیوس ممکن است توسط یک ساده محاسبه رابطه بازگشتی . [3]

                          نمودار خردسالان ویرایش ]

                          نمودار واگنر 8

                          نردبان های موبیوس نقش مهمی در نظریه کودکان خردسال دارند . اولین نتیجه این نوع قضیه از است کلاوس واگنر  ( 1937 ) که نمودار با 5 کوچک را می توان با استفاده از تشکیل باند جمع عملیات به ترکیب گرافهای مسطح و از نردبان موبیوس 8 ؛ به همین دلیل 8 را نمودار واگنر می نامند .

                          گابسر (1996) یک نمودار تقریبا مسطح را گرافی غیر مسطح تعریف می کند که هر خردسال غیرمستقیم برای آن مسطح است. او نشان می دهد که نمودارهای تقریباً مسطح 3 متصل ، نردبانهای موبیوس یا اعضای تعداد کمی از خانواده های دیگر هستند و نمودارهای تقریباً مسطح دیگر را می توان با دنباله ای از عملیات ساده از این شکل گرفت.

                          Maharry (2000) نشان می دهد که تقریباً تمام نمودارهایی که فاقد خرد مکعب هستند می توانند با یک توالی از عملیات ساده از نردبان های Möbius حاصل شوند.

                          شیمی و فیزیک ویرایش ]

                          والبا ، ریچاردز و هالتیوانگر (1982) ابتدا ساختارهای مولکولی را به صورت نردبان موبیوس سنتز کردند و از آن زمان به بعد این ساختار مورد توجه شیمی و استریوگرافی شیمیایی قرار گرفته است [4] ، خصوصاً از نظر فرم نردبان مانند مولکول های DNA . با در نظر گرفتن این کاربرد ، Flapan  ( 1989 ) تقارن های ریاضی تعبیه شده از نردبان های Möbius را در 3 مطالعه می کند . به طور خاص ، همانطور که او نشان می دهد ، هر جاسازی سه بعدی یک نردبان موبیوس با تعداد عجیب و غریب پله ها از نظر توپولوژیک کایرال است: با تغییر شکل مداوم فضا و بدون عبور یک لبه از لبه دیگر ، نمی توان آن را به تصویر آینه تبدیل کرد. از طرف دیگر ، نردبان های موبیوس با تعداد پله های زوج همه در 3 تعبیه شده اند که می توانند به تصاویر آینه ای آنها تغییر شکل دهند.

                          از نردبان های Möbius به عنوان شکل حلقه ابررسانا در آزمایشات برای بررسی تأثیر توپولوژی هادی بر فعل و انفعالات الکترون استفاده شده است. [5]

                          بهینه سازی ترکیبی ویرایش ]

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

                          منبع

                          https://en.wikipedia.org/wiki/M%C3%B6bius_ladder


                          •  

                           


                          •  

                          گراف نسر

                          گراف نسر
                          Kneser graph KG(5,2).svg

                          گراف{\displaystyle KG_{5,2}} با گراف پترسن ایزومورف است.

                          Named afterMartin Kneser
                          راس{\displaystyle \textstyle {\binom {n}{k}}}
                          ضلع{\displaystyle \textstyle {\binom {n}{k}}{\binom {n-k}{k}}/2}
                          رنگ‌آمیزی گراف{\displaystyle \left\{{\begin{array}{ll}n-2k+2&n\geq 2k\\1&{\text{otherwise}}\end{array}}\right.}
                          ویژگی‌هایگراف منتظم
                          arc-transitive
                          قراردادهای نوشتاریKGn,kK(n,k)

                          در نظریه گراف گراف نسر (به انگلیسی: Kneser graph)،{\displaystyle KG_{n,k}}، گرافی است که رأس‌های آن نظیر زیرمجموعه‌های k عضوی از یک مجموعه ی n عضوی است. بین دو رأس یک یال وجود دارد اگر و تنها اگر زیرمجموعه‌های نظیر رأس‌ها ناسازگار باشند (اشتراکشان تهی باشد). این گراف‌ها به نام مارتین نسرر نامگذاری شده‌اند که برای اولین بار آنها را در سال ۱۹۵۵ بررسی کرد.

                           

                          محتویات

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

                          • گراف کامل n رأسی گراف نسر {\displaystyle KG_{n,1}} است.
                          • گراف {\displaystyle KG_{5,2}} با گراف پترسن ایزومورف است.

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

                          • در گراف نسر هر رأس با انتخاب k از n-k رأس دیگر مجاور است.
                          • همانگونه که نسر حدس زد عدد رنگی گراف {\displaystyle KG_{n,k}}{\displaystyle KG_{n,k}} دقیقاً برابر n-2k+۲ است. لوواش در سال ۱۹۷۸ و جاشوآ در سال ۲۰۰۲ برای این فرمول اثبات‌هایی توپولوژیکی ارائه دادند. در سال ۲۰۰۴ ماتوشک اثباتی کاملاً ترکیبیاتی برای آن پیدا کرد.
                          • وقتی n بزرگتر مساوی ۳k باشد گراف نسر همیشه دور هامیلتونی خواهد داشت (چن ۲۰۰۰). محاسبات نشان داده‌اند که همهٔ گراف‌های همبند کنزر با nهای کوچکتر مساوی ۲۷ به جز گراف پترسن، همیلتونی هستند.
                          • اگر n کوچکتر از ۳k باشد گراف نسر هیچ مثلثی نخواهد داشت.

                          منابع

                          گراف مکعبی

                           

                           

                          گراف پترسن یک گراف مکعب است.

                          گراف کامل دوبخشی {\ displaystyle K_ {3،3}}K_ {3،3} نمونه ای از نمودار دو مکعبی است

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

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

                           

                          فهرست

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

                          در سال 1932 ، رونالد ام. فوستر شروع به جمع آوری نمونه هایی از نمودارهای متقارن مکعبی کرد و شروع سرشماری فاستر را تشکیل داد . [1] بسیاری از نمودارهای شناخته شده فردی مکعبی و متقارن هستند ، از جمله نمودار سودمندی ، نمودار پترسن ، نمودار Heawood ، نمودار Möbius – Kantor ، نمودار Pappus ، نمودار Desargues ، نمودار Nauru ، نمودار Coxeter ، نمودار نمودار Tutte – Coxeter ، نمودار Dyck ، نمودار Foster و نمودار Biggs-SmithWT Tutte نمودارهای مکعب متقارن را بر اساس کوچکترین عدد صحیح s طبقه بندی کرده است به طوری که هر دو مسیر جهت دار از طول s را می توان دقیقاً با یک تقارن نمودار برای یکدیگر ترسیم کرد. او نشان داد که s حداکثر 5 است ، و نمونه هایی از نمودارها را با هر مقدار ممکن از s از 1 تا 5 ارائه داد. [2]

                          نمودارهای مکعب نیمه متقارن شامل نمودار خاکستری (کوچکترین نمودار مکعبی نیمه متقارن) ، نمودار لیوبلیانا و 12 قفس Tutte است .

                          نمودار Frucht یکی از پنج کوچکترین گرافهای مکعبی بدون هیچ تقارن است: [3] آن را دارای تنها یک های automorphism نمودار ، های automorphism هویت. [4]

                          مجموعه های رنگ آمیزی و مستقل ویرایش ]

                          با توجه به بروکس 'قضیه هر گراف مکعب متصل به غیر از گراف کامل 4 می توان رنگی با حداکثر سه رنگ. بنابراین ، هر نمودار مکعبی متصل به غیر از 4 دارای یک مجموعه مستقل از حداقل n / 3 رئوس است ، جایی که n تعداد رئوس نمودار است: به عنوان مثال ، بزرگترین کلاس رنگ در 3 رنگ حداقل این تعداد را دارد رگه ها.

                          طبق قضیه ویزینگ ، هر نمودار مکعبی برای رنگ آمیزی لبه به سه یا چهار رنگ نیاز دارد. رنگ آمیزی 3 لبه به عنوان رنگ آمیزی Tait شناخته می شود و پارتیشن لبه های نمودار را به سه تطابق کامل تبدیل می کند . با توجه به قضیه رنگ آمیزی Kőnig ، هر نمودار دو مکعبی دارای یک رنگ آمیزی Tait است.

                          نمودارهای مکعبی بدون پل که رنگ Tait ندارند به عنوان snark شناخته می شوند . آنها شامل نمودار Petersen ، نمودار Tietze ، snacks Blanuša ، snark flower ، snark دو ستاره ، snark Szekeres و snark Watkins هستند . تعداد نامحدود اسنارهای مشخص وجود دارد. [5]

                          توپولوژی و هندسه ویرایش ]

                          نمودارهای مکعبی به طور طبیعی در توپولوژی به چندین روش به وجود می آیند . به عنوان مثال ، اگر کسی یک نمودار را یک مجموعه CW 1 بعدی در نظر بگیرد ، نمودارهای مکعبی عمومی هستند زیرا بیشتر نقشه های پیوست 1 سلولی از اسکلت 0 نمودار جدا نیستند. نمودارهای مکعبی نیز به صورت نمودارهای چند وجهی ساده در سه بعد ، چند وجهی مانند دوازده ضلعی معمولی با خاصیتی که سه چهره در هر راس با هم ملاقات می کنند ، تشکیل می شوند.

                          نمایش تعبیه مسطح به عنوان یک نقشه رمزگذاری شده با نمودار

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

                          همیلتونی ویرایش ]

                          تحقیقات زیادی در مورد همیلتون بودن نمودارهای مکعبی انجام شده است. در سال 1880 ، PG Tait حدس زد که هر نمودار چند وجهی مکعبی دارای مدار همیلتونین است . ویلیام توماس توته یک مثال مخالف برای حدس طایت ، نمودار 46 راس توت ، در سال 1946 ارائه داد. در سال 1971 ، توت حدس زد که همه نمودارهای دو مکعبی همیلتونی هستند. با این حال ، جوزف هورتون نمونه ای نمونه بر روی 96 راس ، نمودار هورتون ، ارائه داده است . [7] بعداً ، مارک الینگهام دو مثال دیگر ساخت: نمودارهای الینگام - هورتون . [8] [9] حدس بارنت ، ترکیبی کاملاً باز از حدس طایت و توت ، بیان می کند که هر نمودار چند وجهی دو مکعبی همیلتونی است. هنگامی که یک نمودار مکعبی همیلتونی است ، علامت گذاری LCF اجازه می دهد تا به طور خلاصه نشان داده شود.

                          اگر یک نمودار مکعبی به طور تصادفی از بین تمام نمودارهای مکعبی n- وارنس انتخاب شود ، به احتمال زیاد همیلتونی است: نسبت نمودارهای مکعبی n -vertex که هامیلتونی هستند ، در حالی که n به بی نهایت می رود ، به یک حد تمایل دارد . [10]

                          دیوید اپستین حدس زد که هر نمودار مکعب n- وورتکس دارای حداکثر 2 n / 3 (تقریباً 1.260 n ) چرخه مشخص هامیلتونی است و نمونه هایی از نمودارهای مکعبی با این تعداد چرخه ارائه داده است. [11] بهترین برآورد اثبات شده برای تعداد چرخه های مشخص هامیلتونی است{\ displaystyle O ({1.276} ^ {n})}O ({1.276} ^ {n})[12]

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

                          مسئله حل نشده در ریاضیات :

                          بزرگترین مسیر ممکن یک{\ displaystyle n}nنمودار مکعب -ترکس؟

                          (مشکلات حل نشده بیشتر در ریاضیات)

                          طول مسیر هر نمودار مکعبی n- وورتکس حداکثر n / 6 است. بهترین شناخته شده پایین ترین حد در مسیر نمودارهای مکعبی 0.082 n است . مشخص نیست که چگونه می توان این شکاف بین این حد پایین و مرز n / 6 بالا را کاهش داد. [13]

                          از لمس دست دادن ، که توسط لئونارد اویلر در سال 1736 به عنوان بخشی از اولین مقاله در مورد تئوری نمودار ثابت شد ، نتیجه می شود که هر نمودار مکعبی تعداد راس های مساوی دارد.

                          قضیه پیترسن بیان می کند که هر نمودار مکعبی بدون پل مکعب مطابقت کاملی دارد . [14] لواسز و پلامر حدس زدند که هر نمودار مکعبی بدون پل دارای تعداد تصاویری از تطابق کامل است. حدس اخیراً اثبات شده است ، نشان می دهد که هر نمودار مکعبی بدون پل با n راس دارای حداقل 2 n / 3656 مطابقت کامل است. [15]

                          الگوریتم ها و پیچیدگی ها ویرایش ]

                          چندین محقق پیچیدگی الگوریتم های زمانی نمایی محدود به نمودارهای مکعبی را مطالعه کرده اند . به عنوان مثال ، با استفاده از برنامه ریزی پویا برای تجزیه مسیر نمودار ، Fomin و Høie نشان دادند که چگونه می توانند حداکثر مجموعه های مستقل خود را در زمان 2 n / 6 + o ( n ) پیدا کنند . [13] مسئله فروشنده دوره گرد در گرافهای مکعبی می تواند در زمان O (1.2312 حل N ) و فضای چند جمله ای. [16] [17]

                          چندین مسئله مهم بهینه سازی نمودار APX سخت است ، به این معنی که ، اگرچه آنها الگوریتم های تقریب دارند که نسبت تقریبی آنها با یک ثابت محدود می شود ، آنها دارای طرح های تقریب زمان چند جمله ای نیستند که نسبت تقریبی آنها به 1 گرایش داشته باشد مگر اینکه P = NP . اینها شامل مشکلات یافتن حداقل پوشش راس ، حداکثر مجموعه مستقل ، حداقل مجموعه غالب و حداکثر برش است . [18] تعداد تقاطع (تعداد حداقل از لبه که در هر عبور رسم ) از یک گراف مکعب است NP-hard استبرای نمودارهای مکعبی اما ممکن است تقریبی باشد. [19] فروشنده دوره گرد مشکل در نمودار مکعب ثابت شده است به NP-hard است برای تقریب به درون هر عامل کمتر از 1153/1152. [20]

                          منبع

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

                          گراف خطی (6)

                          تکرار عملگر گراف خط ویرایش ]

                          van Rooij & Wilf (1965) توالی گرافها را در نظر می گیرند

                           

                          آنها نشان می دهند ، وقتی G یک گراف متصل محدود است ، فقط چهار رفتار برای این توالی امکان پذیر است:

                          • اگر G یک گراف سپس L ( G ) و هر گراف پس از آن در این رشته هستند ریخت به G استاین تنها گرافهای همبنداست که L ( G ) برای G یکسان نیست . [26]
                          • اگر G یک پنجه 1،3 باشد ، L ( G ) و تمام گرافهای بعدی در توالی مثلث هستند.
                          • اگر G یک گراف مسیر باشد ، هر گراف بعدی در دنباله یک مسیر کوتاه تر است تا اینکه در نهایت توالی با یک گراف خالی خاتمه یابد .
                          • در تمام موارد باقیمانده ، اندازه گرافها در این توالی سرانجام بدون محدودیت افزایش می یابد.

                          اگر G همبندنباشد ، این طبقه بندی به طور جداگانه برای هر جز component G اعمال می شود .

                          برای گرافهای همبندکه مسیر نیستند ، تمام تکرارهای عمل گراف خطی به اندازه کافی زیاد ، گرافهایی تولید می کنند که همیلتونین هستند[27]

                          تعمیم ویرایش ]

                          گرافهای داخلی و چند وجهی محدب ویرایش ]

                          مقاله اصلیگراف داخلی

                          وقتی یک گراف مسطح G دارای حداکثر درجه راس سه باشد ، گراف خط آن مسطح است و هر تعبیه مسطح G می تواند به یک تعبیه شده از L ( G ) گسترش یابدبا این حال ، گرافهای مسطحی با درجه بالاتر وجود دارد که گرافهای خطی آنها غیرهمسطح هستنداین موارد شامل ، به عنوان مثال ، 5 ستاره 1،5 ، گراف جواهرات تشکیل شده با اضافه کردن دو مورب غیر تلاقی در یک پنج ضلعی منظم ، و همه چند وجه های محدب با راس درجه چهار یا بیشتر[28]

                          یک ساختار جایگزین ، گراف داخلی ، همزمان با گراف خطی برای گرافهای مسطح با حداکثر درجه سه است ، اما همیشه مسطح استرئوس آن همانند گراف خط است ، اما به طور بالقوه لبه (یال)های کMی دارد: دو راس گراف داخلی مجاور هستند اگر و فقط در صورتی که دو لبه (یال)مربوطه در برخی از چهره های تعبیه شده مسطح متوالی باشندگراف داخلی گراف دوتایی گراف صفحه همان گراف داخلی گراف صفحه اصلی است[29]

                          برای چند وجهی های معمولی یا چند وجهی های ساده ، می توان از طریق هندس به وسیله برش هر راس چند وجهی توسط یک صفحه از طریق نقاط میانی تمام لبه (یال)های برخوردش ، گراف گراف داخلی را نشان داد[30] این عملیات به عنوان کوتاه سازی دوم ، [31] کوتاه شدن منحط ، [32] یا اصلاح شناخته می شود . [33]

                          گرافهای کل ویرایش ]

                          گراف کل T ( G ) یک گراف G دارای عناصر (رئوس یا لبه (یال)هاG است و هر زمان که اتفاق افتاده یا مجاور باشد بین دو عنصر یک لبه (یال)داردگراف کل نیز ممکن است با تقسیم هر لبه (یال)G و سپس گرفتن مربع گراف تقسیم شده بدست آید[34]

                          چند نگاره ویرایش ]

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

                          با این حال ، برای چند گرافها ، تعداد بیشتری جفت گراف غیر همسان وجود دارد که گرافهای خط یکسانی دارندبه عنوان مثال یک گراف دو بخشی کامل 1 ، n دارای گراف خطی همان گراف دو قطبی و ضرب شانون با تعداد لبه (یال)های یکسان استبا این وجود هنوز هم می توان در این مورد از آنالوگ قضیه ایزومورفیسم ویتنی استفاده کرد[12]

                          گرافهای خطیویرایش ]

                          https://upload.wikimedia.org/wikipedia/commons/thumb/9/9d/DeBruijn-as-line-digraph.svg/360px-DeBruijn-as-line-digraph.svg.png

                          ساخت گرافهای دی بروین به عنوان گرافهای تکراری خط

                          همچنین می توان گرافهای خط را به گرافهای هدایت شده تعمیم داد[36] اگر G یک گراف جهت است، آن گراف خط به کارگردانی و یا گراف خط یک راس برای هر لبه (یال)G . دو رئوس نمایانگر لبه (یال)های جهت دار از u به v و از w به x در G با یک لبه (یال)از uv به wx در گراف خطی همبندمی شوند که v = w . یعنی هر لبه (یال)در گراف خط G نشان دهنده یک مسیر دو جهته در G است . گرافهای د بروین ممکن است با تکرار این روند تشکیل گرافهای خط مستقیم ، از یک گراف کامل کارگردانی ، تشکیل شوند . [37]

                          گرافهای خط وزنی ویرایش ]

                          در گراف خط L ( G ) ، هر راس درجه k در گراف اصلی G باعث ایجاد k ( k - 1) / 2 لبه (یال)در گراف خط می شودبرای بسیاری از انواع تجزیه و تحلیل ، این بدان معنی است که گره های درجه بالا در G در گراف خط L ( G ) بیش از حد نشان داده شده اند . به عنوان مثال ، یک قدم زدن تصادفی بر روی رئوس گراف اصلی G را در نظر بگیریداین در امتداد برخی از لبه (یال)های e با برخی از فرکانس f عبور می کند از طرف دیگر ، این لبه (یال)e به یک راس منحصر به فرد ، مثلاً v ، در گراف خط L ترسیم می شودG ) اگر اکنون یک نوع پیاده روی تصادفی را بر روی رئوس گراف خط انجام دهیم ، فرکانس بازدید از v می تواند کاملا با f متفاوت باشد . اگر لبه (یال)e ما در G به گره های درجه O ( k ) همبندباشد ، در گراف خط L ( G ) بیشتر O ( 2 ) عبور داده می شود . به عبارت دیگر، ویتنی تضمین قضیه یکریختی گراف که گراف خط تقریبا همیشه کد می توپولوژی از گراف اصلی Gصادقانه اما تضمین نمی کند که پویایی در این دو گراف یک رابطه ساده داردیک راه حل ساختن گراف خط وزنی است ، یعنی یک گراف خطی با لبه (یال)های وزن دار . چندین روش طبیعی برای انجام این کار وجود دارد[38] به عنوان مثال اگر لبه (یال)های d و e در گراف G در یک راس v با درجه k قرار داشته باشند ، در گراف خط L ( G ) می توان به لبه (یال)اتصال دو راس d و e وزن 1 / ( k) داد - 1) به این ترتیب هر لبه (یال)در G(به شرطی که هیچ یک از انتها به راس درجه 1 همبندنباشد) دارای مقاومت 2 در گراف خط L ( G ) مربوط به دو انتهای لبه (یال)در G خواهد بودساده است که این تعریف از گراف خط وزنی را به مواردی که گراف اصلی G کارگردانی یا حتی وزنی شده است ، گسترش دهیم[39] اصل در همه موارد این است که اطمینان حاصل شود گراف خط L ( G ) دینامیک و همچنین توپولوژی گراف اصلی G را منعکس می کند .

                          گرافهای خط هایپراگراف ویرایش ]

                          مقاله اصلیگراف خطی یک ابر نوشتار

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

                          گراف عدم انسجام ویرایش ]

                          گراف disjointness از G ، مشخص D ( G ) است، به روش زیر ساخته شده: برای هر یال در G ، یک راس در D ( G ). برای هر دو لبه (یال)در G که نمی راس مشترک است، یک لبه (یال)بین رئوس مربوط به خود را در D ( G ). [40] به عبارت دیگر ، D ( G ) گراف مکمل L ( G ) استیک دسته در D ( G ) مربوط به یک مجموعه مستقل در L ( G ) است و بالعکس.

                          منبع

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

                          گراف خطی (5)

                           

                          زیرنویس های ممنوع ویرایش ]

                          https://upload.wikimedia.org/wikipedia/commons/thumb/6/6c/Forbidden_line_subgraphs.svg/300px-Forbidden_line_subgraphs.svg.png

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

                          خصوصیات دیگر گرافهای خط در Beineke (1970) به اثبات رسیده است (و قبلاً بدون اثبات توسط Beineke (1968) گزارش شد ). وی نشان داد که نه گراف حداقل وجود دارد که گراف خطی نیستند ، به طوری که هر گراف که گراف خطی نباشد ، یکی از این نه گراف را به عنوان یک زیرگراف القایی دارد . یعنی یک گراف یک گراف خطی است اگر و فقط اگر هیچ زیر مجموعه ای از رئوس آن یکی از این نه گراف را القا نکنددر مثال بالا ، چهار رئوس بالایی یک پنجه را القا می کند (یعنی یک گراف دو بخشی کامل 1،3) ، در بالا سمت چپ تصویر زیرنویس های ممنوع نشان داده شده استبنابراین ، با توصیف Beineke ، این مثال نمی تواند یک گراف خطی باشدبرای گرافهایی با حداقل درجه حداقل 5 ، فقط شش زیرگراف در ستون های چپ و راست شکل در توصیف مورد نیاز است[25]

                          الگوریتم ها ویرایش ]

                          روسوپولوس (1973) و لهوت (1974) الگوریتم های زمان خطی را برای شناسایی گرافهای خطی و بازسازی گرافهای اصلی آنها توصیف کردندSysło (1982) این روش ها را به گرافهای جهت دار تعمیم داد . Degiorgi & Simon (1995) یک ساختار داده کارآمد را برای حفظ گراف پویا ، منوط به درج و حذف راس ، و حفظ نمایش ورودی به عنوان گراف خط (در صورت وجود) در زمان متناسب با تعداد لبه (یال)های تغییر یافته توصیف کرده است. هر مرحله

                          الگوریتم های روسوپولوس (1973) و لهوت (1974) بر اساس خصوصیات گرافهای خطی شامل مثلث های عجیب و غریب (مثلث در گراف خط با ویژگی که یک راس دیگر در مجاورت تعداد عجیب و غریب از راس های مثلث وجود دارد) استبا این حال ، الگوریتم Degiorgi & Simon (1995) فقط از قضیه ایزومورفیسم ویتنی استفاده می کنداین نیاز به شناسایی حذف هایی است که باعث می شود گراف باقیمانده به یک گراف خطی تبدیل شود ، پیچیده است ، اما در صورت تخصصی بودن مسئله شناسایی استاتیک ، فقط درج باید انجام شود و الگوریتم مراحل زیر را انجام می دهد:

                          • گراف ورودی L را با اضافه کردن یک به یک راس ، در هر مرحله انتخاب یک راس برای اضافه کردن که در مجاورت حداقل یک راس قبلا اضافه شده است ، ساخت در حالی که رئوس را به L اضافه می کنید ، یک گراف G را حفظ کنید که L = L ( G ) برای آن باشداگر الگوریتم هرگز نتواند گراف مناسب G پیدا کند ، ورودی یک گراف خط نیست و الگوریتم خاتمه می یابد.
                          • هنگام افزودن راس v به گراف L ( G ) که G دارای چهار رئوس یا کM است ، ممکن است اینگونه باشد که گراف گراف خط منحصر به فرد نباشداما در این حالت گراف افزوده به اندازه کافی کوچک است که با جستجوی نیروی بی رحم در زمان ثابت می توان نمایشی از آن را به عنوان یک گراف خطی پیدا کرد .
                          • هنگام افزودن یک راس v به گراف بزرگتر L که برابر با گراف خط گراف دیگر G است ، بگذارید S زیرنویس G باشد که توسط لبه (یال)های مربوط به همسایگان v در L تشکیل شده است . بررسی کنید که S دارای یک راس است که از یک راس یا دو راس غیر مجاور تشکیل شده استاگر دو راس در پوشش وجود دارد ، G را با افزودن یک لبه (یال)(مربوط به v ) که این دو راس را به هم همبندمی کند ، افزایش دهید . اگر فقط یک راس در پوشش وجود دارد ، سپس یک راس جدید به G ، مجاور این راس اضافه کنید.

                          هر مرحله یا به زمان ثابت نیاز دارد ، یا شامل یافتن یک راس از اندازه ثابت در گراف S است که اندازه آن متناسب با تعداد همسایگان v است . بنابراین ، کل زمان برای کل الگوریتم متناسب با مجموع تعداد همسایگان تمام رئوس است که (با لمس دست دادن ) متناسب با تعداد لبه (یال)های ورودی است.

                          منبع

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

                          گراف خطی (4)

                           

                          سایر خانواده های گراف مربوط ویرایش ]

                          تمام گرافهای خطی گرافهای بدون پنجه هستند ، گرافهایی بدون زیرنویس القایی به صورت یک درخت سه برگ[20] مانند گرافهای بدون پنجه به طور کلی ، هر گراف خط همبندL ( G ) با تعداد زوج دارای یک لبه (یال)کاملاً منطبق است . [21] به طور معادل ، این بدان معنی است که اگر گراف زیر G تعداد زوجی از لبه (یال)ها داشته باشد ، می توان لبه (یال)های آن را به مسیرهای دو لبه (یال)تقسیم کرد.

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

                          همه مقادیر ویژه از ماتریس مجاورت  از یک گراف خط حداقل −2 استدلیل این امر این است که  می تواند به صورت  ، جایی که   ماتریس وقوع بدون علامت گراف پیش خط است و هویت است به خصوص، است ماتریس Gramian تمام گراف ها با این ویژگی شده اند به نام گراف خط تعمیم: یک سیستم از بردار[24]

                          شخصیت پردازی و تشخیص ویرایش ]

                          پارتیشن کلیک ویرایش ]

                          https://upload.wikimedia.org/wikipedia/commons/thumb/e/e8/Line_graph_clique_partition.svg/280px-Line_graph_clique_partition.svg.png

                          تقسیم گراف خطی به صورت کلیکی

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

                          از وجود چنین پارتیشنی به صورت کلیکی می توان برای مشخص کردن گرافهای خط استفاده کرد: یک گراف L گراف خطی گراف یا چند گراف دیگری است اگر و فقط در صورت امکان یافتن مجموعه ای از کلیک ها در L (اجازه برخی از موارد کلیک ها به صورت یک راس واحد هستند) که لبه (یال)های L را تقسیم می کنند ، به طوری که هر راس L دقیقاً به دو دسته مربوط می شود[20] این گراف خطی یک گراف است (به جای چند گراف) اگر این مجموعه کلیها شرایط دیگری را تأمین کند که هیچ دو راس L هر دو در همان دو کلیک نیستبا توجه به چنین خانواده ای از کلیک ها ، گراف زیر G برای آن Lگراف خطی است که می توان با ساختن یک راس در G برای هر دسته ، و یک لبه (یال)در G برای هر راس در L با نقاط انتهایی آن ، دو کلیک حاوی راس در L است . با توجه به نسخه قوی قضیه ایزومورفیسم ویتنی ، اگر گراف زیر G بیش از چهار رئوس داشته باشد ، فقط یک پارتیشن از این نوع وجود دارد.

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

                           

                          در این مثال ، لبه (یال)ها از سمت راست و چهار راس به سمت بالا ، چپ و راست می روند هیچ کلیکی مشترک ندارندبنابراین ، هر قسمت از لبه (یال)های گراف به صورت کلیکی باید حداقل یک دسته برای هر یک از این سه لبه (یال)داشته باشد ، و این سه کلیک همگی در آن راس مرکزی تلاقی می یابند ، و این شرط ظاهر شدن هر راس دقیقاً در دو دسته را نقض می کندبنابراین گراف نشان داده شده گراف خطی نیست.

                          گراف خطی (3)

                           

                          گرافهای کاملاً منظم و کامل ویرایش ]

                          https://upload.wikimedia.org/wikipedia/commons/thumb/6/6c/Line_perfect_graph.svg/240px-Line_perfect_graph.svg.png

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

                          گراف خط از گراف کامل K N نیز به عنوان شناخته شده گراف مثلثی از جانسون گراف J ( N ، 2)، و یا مکمل از در Kneser گراف KG N ، 2 . گرافهای مثلثی توسط طیف هایشان مشخص می شوند ، به استثنای n = 8. [13] همچنین ممکن است مشخص شود (بازهم به استثنای 8 ) به عنوان گرافهای کاملاً منظم با پاراMهای srg ( n ( n  - 1) / 2، 2 ( n  - 2) ، n  - 2 ، 4).[14] سه گراف کاملاً منظم با همان پاراMها و طیف L ( K 8 ) گرافهای Chang هستند که ممکن است با تغییر گراف از L ( K 8 )بدست آیند.

                          گراف خطی یک گراف دو بخشی کامل است ( به قضیه Kőnig مراجعه کنید ) ، اما همانطور که نمونه گراف پنجه نشان می دهد ، لازم نیست که دو بخشی باشدگرافهای خط گرافهای دو بخشی یکی از عناصر اصلی ساخت گرافهای کامل را تشکیل می دهد که در اثبات قضیه قوی گراف کامل استفاده می شود . [15] یک مورد خاص از این گرافها گرافهای خروجی ، گرافهای خطی گرافهای کامل از دو قسمت است . مانند گرافهای خط گرافهای کامل ، می توان آنها را به استثنای تعداد رئوس ، تعداد لبه (یال)ها و تعداد همسایگان مشترک برای نقاط مجاور و غیر مجاور مشخص کردیک مورد استثنایی L ( K) است4،4 ) ، که پاراMهای خود را با گراف Shrikhande به اشتراک می گذارد . هنگامی که هر دو طرف تقسیم دو راس به همان اندازه باشد ، این گرافها دوباره کاملا منظم هستند[16]

                          به طور کلی ، می توان گفت گراف G یک گراف کامل خطی است اگر L ( G ) یک گراف کامل باشدگرافهای کامل خطی دقیقاً گرافهایی هستند که شامل یک دور ساده با طول فرد بیش از سه نیستند[17] به طور معادل ، یک گراف کاملاً مناسب است اگر و فقط اگر هر یک از اجزای دو به هم پیوسته آن دو بخشی باشد یا از شکل 4 (چهار ضلعی) یا 1،1 ، n باشد (کتابی از یک یا چند مثلث که همه دارای یک لبه (یال)مشترک[18] هر گراف کامل خط خود عالی است[19]

                          گراف خطی (2)

                           

                          مثال ویرایش ]

                          شکل های زیر یک گراف (سمت چپ ، با راس های آبی) و گراف خط آن (راست ، با راس های سبز) را نشان می دهدهر راس گراف خط با برچسب جفت نقاط انتهایی لبه (یال)مربوطه در گراف اصلی نشان داده شده استبه عنوان مثال ، رأس سبز در سمت راست با برچسب 1،3 مربوط به لبه (یال)سمت چپ بین رأس های آبی 1 و 3 است. رأس سبز 1،3 در مجاورت سه رأس سبز دیگر است: 1،4 و 1،2 (مربوط به به لبه (یال)هایی که نقطه پایانی 1 را در گراف آبی به اشتراک می گذارند) و 4،3 (مربوط به یک لبه (یال)مشترک نقطه انتهایی 3 در گراف آبی).

                          • https://upload.wikimedia.org/wikipedia/commons/thumb/3/36/Line_graph_construction_1.svg/135px-Line_graph_construction_1.svg.png

                          گراف G

                           

                          • https://upload.wikimedia.org/wikipedia/commons/thumb/a/a1/Line_graph_construction_2.svg/135px-Line_graph_construction_2.svg.png

                          رئوس در L (G) از لبه (یال)های G ساخته شده است

                           

                          • https://upload.wikimedia.org/wikipedia/commons/thumb/0/05/Line_graph_construction_3.svg/135px-Line_graph_construction_3.svg.png

                          لبه (یال)های اضافه شده در L (G)

                           

                          • https://upload.wikimedia.org/wikipedia/commons/thumb/5/5b/Line_graph_construction_4.svg/128px-Line_graph_construction_4.svg.png

                          گراف خط L (G)

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

                          خصوصیات ترجمه شده گراف اساسی ویرایش ]

                          خصوصیات یک گراف G که فقط به مجاورت بین لبه (یال)ها بستگی دارد ، می تواند در L ( G ) به خصوصیات معادل ترجمه شود که به مجاورت بین رئوس بستگی داردبه عنوان مثال ، تطبیق در G مجموعه ای از لبه (یال)ها است که دو تا از آنها مجاور نیستند و مربوط به مجموعه ای از رئوس در L ( G ) است که هیچ دو مجاور نیستند ، یعنی یک مجموعه مستقل . [4]

                          بدین ترتیب،

                          • گراف خط یک گراف همبنداستاگر G همبندباشد ، شامل مسیری است که هر دو لبه (یال)آن را بهم همبندمی کند ، که به یک مسیر در L ( G ) تبدیل می شود که شامل هر دو راس L ( G ) استبا این حال ، یک گراف G که دارای برخی از رئوس جدا شده است و بنابراین قطع شده است ، ممکن است دارای یک گراف خط همبندباشد[5]
                          • یک گراف خط دارای نقطه بیان اگر و تنها اگر گراف زمینه دارای یک پل است که نه نقطه پایانی است یک درجه[2]
                          • برای یک گراف G با n را راس و M لبه، تعداد رئوس گراف خط L ( G ) است M و تعداد لبه (یال)های L ( G ) نیمی از مجموع مربعات از است درجه رئوس در G ، منهای M . [6]
                          • یک مجموعه مستقل در L ( G ) مربوط به مطابقت در G است . به طور خاص ، یک مجموعه حداکثر مستقل در L ( G ) با حداکثر مطابقت در مطابقت دارد . از آنجا که حداکثر تطابق ممکن است در زمان چند جمله ای پیدا شود ، بنابراین ممکن است حداکثر مجموعه های مستقل گرافهای خط ، با وجود سختی مشکل حداکثر مجموعه مستقل برای خانواده های کلی گرافها[4] به طور مشابه ، مجموعه ای مستقل از رنگین کمان در L ( G ) مربوط به رنگین کمان است که در مطابقت دارد .
                          • لبه (یال)عدد رنگی از یک گراف G به برابر است راس عدد رنگی گراف خط خود را L ( G ). [7]
                          • گراف خطی یک گراف لبه (یال)متعدی است راس-متعدی . از این ویژگی می توان برای ایجاد خانواده هایی از گراف استفاده کرد که (مانند گراف پیترسن ) راس-انتقالی هستند اما گرافهای Cayley نیستند : اگر G یک گراف حاشیه ای است که حداقل پنج راس دارد ، دو قسمت نیست و راس فرد دارد درجه ، سپس L ( G ) یک گراف غیر کایلی راس-انتقالی است[8]
                          • اگر یک گراف G دارای یک دور اویلر ، این است که، اگر G همبنداست و حتی تعداد از لبه (یال)در هر راس، پس از آن گراف خط از G است هامیلتونی . با این حال ، همه دور های همیلتون در گرافهای خط از دور های اولر به این ترتیب حاصل نمی شوندبه عنوان مثال ، گراف خط یک گراف هامیلتونی G خود همیلتونی است ، صرف نظر از اینکه G نیز اولری باشد[9]
                          • اگر دو گراف ساده یکدست نباشد ، گرافهای خطی آنها نیز نامتقارن استویتنی یکریختی گراف قضیه یک محاوره با این برای همه اما یک جفت از گراف فراهم می کند.
                          • در چارچوب نظریه پیچیده شبکه ، گراف خطی یک شبکه تصادفی بسیاری از خصوصیات شبکه مانند خاصیت جهان کوچک (وجود مسیرهای کوتاه بین همه جفت رأس ها) و شکل توزیع درجه آن را حفظ می کند . [10] Evans & Lambiotte (2009) مشاهده کردند که هر روشی برای یافتن خوشه های راس در یک شبکه پیچیده می تواند بر روی گراف خط اعمال شود و به جای آن برای خوشه بندی لبه (یال)های آن استفاده شود.

                          قضیه ایزومورفیسم ویتنی ویرایش ]

                          https://upload.wikimedia.org/wikipedia/commons/thumb/e/eb/Diamond_graph.svg/120px-Diamond_graph.svg.png

                          گراف الماس ، یک استثنا برای این قضیه قوی ویتنی

                          اگر گرافهای خطی دو گراف متصل به هم یکدست نباشند ، گرافهای زیرمجموعه هستند ، مگر در مورد گراف مثلث و پنجه 1،3 ، که دارای گرافهای خط غیر همسان هستند اما خود منسجم نیستند[3]

                          علاوه بر و 1،3 ، گرافهای کوچک استثنایی دیگری نیز با این ویژگی وجود دارد که گراف خط آنها دارای درجه تقارن بالاتری از خود گراف استبه عنوان مثال ، گراف الماس 1،1،2 (دو مثلث مشترک لبه) دارای چهار شکل گیری گراف است اما گراف خط آن 1،2،2هشت تا دارددر تصویر گراف الماس نشان داده شده ، چرخش 90 درجه گراف تقارن گراف نیست ، بلکه تقارن گراف خط آن استبا این حال ، همه این موارد استثنایی حداکثر چهار راس دارندیک نسخه تقویت شده از قضیه ایزومورفیسم ویتنی بیان می کند که ، برای گرافهای همبندبا بیش از چهار راس ، بین یکسان سازی گرافها و ایزومورفیسم گرافهای خط آنها یک به یک مطابقت وجود دارد[11]

                          آنالوگ از ریخت ویتنی قضیه برای گراف خط از ثابت شده است گرافهای چندگانه ، اما بیشتر در این مورد پیچیده است[12]

                          تئوری گراف - تطبیق ها

                           

                           

                           صفحه قبلی

                          صفحه بعد  

                          نمودار منطبق ، یک زیر نمودار از نمودار است که در آن هیچ لبه مجاور یکدیگر وجود ندارد. به سادگی ، نباید هیچ راس مشترکی بین دو لبه وجود داشته باشد.

                          تطابق

                          بگذارید 'G' = (V ، E) یک نمودار باشد. به یک زیرگراف M (G) مطابق گفته می شود ، اگر هر راس G با حداکثر یک لبه در M اتفاق بیفتد ، به عنوان مثال ،

                          deg (V) ≤ 1 ∀ V ∈ G

                          این بدان معناست که در نمودار مطابق M (G) ، رئوس باید درجه 1 یا 0 داشته باشند ، جایی که لبه ها باید از نمودار G اتفاق بیفتند.

                          علامت گذاری - M (G)

                          مثال

                          نمودار تطبیققانون تطبیق

                          در یک تطبیق ،

                          اگر deg (V) = 1 ، سپس (V) گفته می شود که مطابقت دارد

                          اگر deg (V) = 0 ، پس از آن (V) مطابقت ندارد.

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

                          تطبیق حداکثر

                          اگر هیچ لبه دیگری از "G" به M اضافه نشود ، یک M منطبق از نمودار "G" به حداکثر گفته می شود .

                          مثال

                          حداکثر تطبیق G

                          M1 ، M2 ، M3 از نمودار بالا حداکثر مطابقت G است.

                          حداکثر تطبیق

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

                          به تعداد لبه ها در حداکثر تطبیق "G" عدد مطابقت آن گفته می شود .

                          مثال

                          حداکثر تطبیق

                          برای نمودار ارائه شده در مثال فوق ، M1 و M2 حداکثر مطابقت "G" و عدد مطابقت آن 2 است. از این رو با استفاده از نمودار G ، ما فقط می توانیم زیرگرافها را فقط با حداکثر 2 لبه تشکیل دهیم. از این رو عدد تطبیق را دو داریم.

                          تطبیق کامل

                          مطابقت (M) نمودار (G) مطابقت کامل دارد ، اگر هر راس نمودار g (G) دقیقاً به یک لبه مطابقت (M) برخورد کند ، به عنوان مثال ،

                          deg (V) = 1 V

                          درجه هر راس در زیرگراف باید درجه 1 باشد.

                          مثال

                          در نمودارهای زیر ، M1 و M2 نمونه هایی از مطابقت کامل G است.

                          تطبیق کامل

                          توجه - هر تطبیق کامل نمودار همچنین یک تطبیق حداکثر نمودار است ، زیرا هیچ فرصتی برای اضافه کردن یک لبه دیگر در یک نمودار تطبیق کامل وجود ندارد.

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

                          مثال

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

                          توجه - معکوس جمله فوق الذکر صحیح نیست. اگر G دارای راسهای زوج باشد ، M1 نیازی به کامل بودن ندارد.

                          مثال

                          تعداد رئوس

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

                          منبع

                          https://www.tutorialspoint.com/graph_theory/graph_theory_matchings.htm

                          یاداشت 2 گراف

                          • گراف 1-منظم با n=2k راس عبارتست از یک گراف که از k تا K2 دزست گردیده است که مقدار های ویژه آن 1و -1 با تکرر هر کدام k هست
                          • مکمل گراف 1-منظم با n=2k راس عبارتست از یک گراف با n=2k راس دزست گردیده است که مقدار های ویژه آن 2k-2 با تکرر1 و 2- با تکررk-1 ,و صفر با تکرر k است. مکمل گراف یک گراف منظم با درجه 2k-2 است

                          نمودار اولر | مسیر اولر | مدار اویلر

                          نمودار اولر | مسیر اولر | مدار اویلر

                          نظریه نمودار

                          انواع نمودارها-

                           

                          قبل از اینکه این مقاله را مرور کنید ، مطمئن شوید که مقاله قبلی درباره انواع نمودارها را در تئوری نمودار مرور کرده اید .

                           

                          ما در این زمینه صحبت کرده ایم-

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

                           

                           

                          در این مقاله ، در مورد نمودارهای اولر بحث خواهیم کرد.

                           

                          نمودار اولر-

                           

                          یک نمودار اولر ممکن است به صورت زیر تعریف شود:

                           

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

                           

                          یا

                          نمودار اولر یک نمودار متصل است که شامل یک مدار اویلر است.

                           

                          نمودار اولر نمودار-

                           

                          نمودار زیر مثالی از نمودار اولر است -

                           

                           

                          اینجا،

                          • این نمودار یک نمودار متصل است و تمام رئوس آن از یک درجه هستند.
                          • بنابراین ، این یک نمودار اولر است.

                           

                          روش دیگر ، نمودار فوق شامل یک مدار اویلر BACEDCB است ، بنابراین یک نمودار اویلر است.

                           

                          همچنین نمودار - Planar را بخوانید

                           

                          مسیر اولر-

                           

                          مسیر اولر با نام Euler Trail یا Euler Walk نیز شناخته می شود .

                           

                          • اگر در نمودار متصل یک دنباله وجود داشته باشد که حاوی تمام لبه های نمودار باشد ، آن دنباله به عنوان دنباله اویلر خوانده می شود.

                          یا

                          • اگر در نمودار متصل پیاده روی وجود داشته باشد که دقیقاً یک بار با تکرار راسها یا بدون تکرار آنها از هر لبه نمودار بازدید کند ، چنین پیاده روی را پیاده روی اولر می نامند.

                           

                          توجه داشته باشید

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

                           

                          مثالهای مسیر اویلر-

                           

                          نمونه هایی از مسیر اولر به شرح زیر است:

                           

                           

                          مدار اویلر-

                           

                          مدار اولر با نام Euler Cycle یا Euler Tour نیز شناخته می شود .

                           

                          • اگر یک مدار در نمودار متصل وجود داشته باشد که شامل تمام لبه های نمودار باشد ، آن مدار را مدار اویلر می نامند.

                          یا

                          • اگر در نمودار متصل پیاده روی وجود داشته باشد که در همان راس شروع و به پایان برسد و دقیقاً یک بار با تکرار رأس یا بدون تکرار از هر لبه نمودار بازدید کند ، بنابراین چنین پیاده روی به عنوان مدار اویلر خوانده می شود.

                          یا

                          • دنباله اویلر که در همان راس شروع و پایان می یابد به عنوان مدار اویلر خوانده می شود.

                          یا

                          • از مسیر دنباله دار اولر به عنوان مدار اویلر نام برده می شود.

                           

                          توجه داشته باشید

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

                           

                          مثالهای مدار اویلر-

                           

                          نمونه هایی از مدار اویلر به شرح زیر است:

                           

                           

                          نمودار نیمه اویلر-

                           

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

                           

                          بنابراین ، برای اینکه یک نمودار یک نمودار نیمه اولر باشد ، باید دو شرط زیر رعایت شود -

                          • نمودار باید متصل باشد.
                          • نمودار باید حاوی دنباله اویلر باشد.

                           

                          مثال-

                           

                           

                          اینجا،

                          • این نمودار شامل دنباله اولر BCDBAD است.
                          • اما حاوی مدار اویلر نیست.
                          • بنابراین ، این یک نمودار نیمه اولری است.

                           

                          همچنین نمودار دو طرفه را بخوانید

                           

                          یادداشت های مهم-

                           

                          توجه -01:

                           

                          برای بررسی اینکه آیا هر نمودار یک نمودار اولر است یا نه ، ممکن است از یکی از دو روش زیر استفاده شود -

                          • اگر نمودار متصل باشد و حاوی مدار اویلر باشد ، نمودار آن اویلر است.
                          • اگر تمام رئوس نمودار از یک درجه باشند ، یک نمودار اویلر است.

                           

                          توجه -02:

                           

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

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

                           

                          Note-03:

                           

                          برای بررسی اینکه آیا هر نمودار یک نمودار نیمه اولر است یا نه ،

                          • فقط مطمئن شوید که متصل است و حاوی دنباله اویلر است.
                          • اگر نمودار متصل باشد و حاوی دنباله اویلر باشد ، در غیر این صورت نمودار یک نمودار نیمه اولر است.

                           

                          Note-04:

                           

                          برای بررسی اینکه آیا هر گرافی حاوی دنباله اولر است یا خیر ،

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

                           

                          Note-05:

                           

                          • اگر یک نمودار حاوی مدار اویلر باشد ، قطعاً شامل یک مسیر Euler خواهد بود.
                          • اگر نمودار دارای یک مسیر اویلر باشد ، ممکن است حاوی مدار اویلر باشد یا نباشد.

                           

                          Note-06:

                           

                          • نمودار اولر قطعاً یک نمودار نیمه اولر است.
                          • اما نمودار نیمه اولر ممکن است نمودار اولر باشد یا نباشد.

                           

                          مشکلات عملی براساس گرافهای EULER در نظریه گراف-

                           

                          چالش ها و مسائل-

                           

                          کدام یک از نمودارهای اولر است / هستند؟

                           

                           

                          راه حل ها-

                           

                          اگر تمام رئوس یک نمودار از درجه یکسان باشند ، در غیر این صورت نمودار یک نمودار اولر است.

                           

                          با استفاده از قانون فوق ،

                          الف) این یک نمودار اولر است.

                          ب) نمودار اولر نیست.

                          ج) نمودار اولر نیست.

                          د) نمودار اولر نیست.

                          ه) نمودار اولر است.

                          و) نمودار اولر نیست.

                           

                          برای درک بهتر در مورد نمودارهای اولر در تئوری نمودار ،

                          این سخنرانی ویدئویی را مشاهده کنید

                           

                          مقاله بعدی- نمودار همیلتونین

                           

                          یادداشت های بیشتر و سایر مطالب مطالعه تئوری نمودار را دریافت کنید.

                          با مراجعه به کانال YouTube ما LearnVidFun ، سخنرانی های ویدیویی را تماشا کنید .

                          خلاصه

                          نمودار اولر |  مسیر اولر |  مدار اویلر

                          نام مقاله

                          نمودار اولر | مسیر اولر | مدار اویلر

                          شرح

                          نمودار اویلر در تئوری نمودار - نمودار اویلر یک نمودار متصل است که تمام رئوس آن از یک درجه هستند. مثالهای نمودار اولر. Euler Path and Euler Circuit- Euler Path یک دنباله در نمودار متصل است که شامل تمام لبه های نمودار است. مسیر دنباله دار اولر به عنوان مدار اویلر خوانده می شود.

                          نویسنده

                          آکشی سینگال

                          نام ناشر

                          دروازه ویدیالی

                          آرم ناشر

                          منبع

                          https://www.gatevidyalay.com/euler-graph-euler-trail-euler-circuit/

                          رنگ آمیزی نمودار در تئوری نمودار | تعداد رنگی نمودارها


                          رنگ آمیزی نمودار-

                           

                          Graph Coloring فرایندی است که رنگها را به رئوس یک نمودار اختصاص می دهد

                           

                          به گونه ای که به هیچ دو راس مجاور آن یک رنگ اختصاص داده نشده است.

                           

                          • Graph Coloring به رنگ Vertex Coloring نیز گفته می شود .
                          • این تضمین می کند که هیچ لبه ای در نمودار وجود ندارد که رئوس انتهایی آن با همان رنگ رنگی باشد.
                          • از چنین گرافی به عنوان نمودار رنگی مناسب نام برده می شود .

                           

                          نمودار رنگ آمیزی نمودار-

                           

                          نمودار زیر مثالی از نمودار به درستی رنگی است -

                           

                           

                          در این نمودار ،

                          • هیچ دو راس مجاور با یک رنگ رنگی نیستند.
                          • بنابراین ، یک نمودار رنگی مناسب است.

                           

                          برنامه های رنگ آمیزی نمودار-

                           

                          برخی از کاربردهای مهم رنگ آمیزی نمودار به شرح زیر است:

                          • رنگ آمیزی نقشه
                          • برنامه ریزی وظایف
                          • تهیه جدول زمانی
                          • وظیفه
                          • حل تعارض
                          • سودوکو

                           

                          شماره رنگی-

                           

                          Chromatic Number حداقل رنگ مورد نیاز برای رنگ آمیزی صحیح هر نمودار است.

                           

                          یا

                          Chromatic Number حداقل رنگ مورد نیاز برای رنگ آمیزی هر نمودار است

                          به گونه ای که به هیچ دو راس مجاور آن یک رنگ اختصاص داده نشده است.

                           

                          شماره اعداد رنگی-

                           

                          نمودار زیر را در نظر بگیرید-

                           

                           

                          در این نمودار ،

                          • هیچ دو راس مجاور با یک رنگ رنگی نیستند.
                          • حداقل رنگ مورد نیاز برای رنگ آمیزی صحیح رئوس = 3.
                          • بنابراین ، تعداد رنگی این نمودار = 3 است.
                          • ما نمی توانیم این نمودار را به درستی با کمتر از 3 رنگ رنگ کنیم.

                           

                           

                          تعداد رنگی نمودارها-

                           

                          تعداد رنگی برخی از انواع معمول نمودارها به شرح زیر است -

                           

                          1. نمودار چرخه-

                           

                          • یک نمودار ساده از رئوس 'n' (n> = 3) و 'n' لبه های تشکیل دهنده یک چرخه طول 'n' به عنوان نمودار چرخه نامیده می شود.
                          • در نمودار چرخه ، همه رئوس درجه 2 هستند.

                           

                          شماره رنگی

                          • اگر تعداد رئوس در نمودار چرخه زوج باشد ، عدد رنگی آن = 2 است.
                          • اگر تعداد رئوس نمودار چرخه فرد باشد ، عدد رنگی آن = 3 است.

                           

                          مثال ها-

                           

                           

                          2. نمودارهای مسطح-

                           

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

                           

                          شماره رنگی

                          تعداد رنگی هر نمودار مسطح

                          = کمتر یا برابر با 4

                           

                          مثال ها-

                           

                          • تمام نمودارهای چرخه فوق نیز نمودار مسطحی هستند.
                          • تعداد رنگی هر نمودار کمتر یا برابر با 4 است.

                           

                           

                          3. نمودارهای کامل-

                           

                          • نمودار كامل نموداري است كه در آن هر دو راس مشخص با دقيقاً يك لبه به هم متصل شوند.
                          • در یک نمودار کامل ، هر راس با هر راس دیگر مرتبط است.
                          • بنابراین برای درست کردن آن ، به همان تعداد رئوس رنگ مختلف در نمودار  نیاز است.

                           

                          شماره رنگی

                          تعداد رنگی نمودار کامل

                          = تعداد رئوس آن نمودار کامل

                           

                          مثال ها-

                           

                           

                          4. نمودارهای دو طرفه

                           

                          • دوبخشی نمودار شامل دو مجموعه از رئوس X و Y
                          • لبه ها فقط رئوس X را به رئوس Y متصل می کنند ، نه راس درون یک مجموعه.

                           

                          شماره رنگی

                          تعداد رنگی هر نمودار دو بخشی

                          = 2

                           

                          مثال-

                           

                           

                          5. درختان-

                           

                          • درخت نوع خاصی از گراف همبند که در آن هیچ مدار وجود ندارد.
                          • هر درخت یک نمودار دو بخشی است.
                          • بنابراین ، تعداد رنگی یک درخت با هر تعداد راس = 2.

                           

                          شماره رنگی

                          تعداد رنگی هر درخت

                          = 2

                           

                          مثال ها-

                           

                           

                          خلاصه

                          رنگ آمیزی نمودار در تئوری نمودار |  تعداد رنگی نمودارها

                          نام مقاله

                          رنگ آمیزی نمودار در تئوری نمودار | تعداد رنگی نمودارها

                          شرح

                          نمودار رنگ آمیزی در تئوری نمودار - رنگ آمیزی نمودار فرآیندی برای تعیین رنگ به رئوس است به طوری که هیچ دو راس مجاور یک رنگ نیست. Chromatic Number of a Graph حداقل تعداد رنگهای مورد نیاز برای رنگ آمیزی صحیح نمودار است.

                          نویسنده

                          آکشی سینگال

                          نام ناشر

                          دروازه ویدیالی

                          آرم ناشر

                          منبع

                          https://www.gatevidyalay.com/graph-coloring-chromatic-number/

                          نمودار همیلتونین | مسیر همیلتونین | مدار همیلتونین


                          انواع نمودارها-

                          قبل از اینکه این مقاله را مرور کنید ، مطمئن شوید که مقاله قبلی درباره انواع نمودارها را در تئوری نمودار مرور کرده اید .

                          ما در این زمینه صحبت کرده ایم-

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

                          در این مقاله ، ما در مورد نمودارهای همیلتونین بحث خواهیم کرد.

                          نمودار هامیلتونی-

                          نمودار همیلتونین ممکن است به صورت زیر تعریف شود:

                          اگر در نمودار متصل پیاده روی بسته ای وجود داشته باشد که دقیقاً یک بار از هر راس نمودار بازدید می کند

                          (به جز شروع راس) بدون تکرار لبه ها ،

                          سپس چنین گرافی به عنوان نمودار همیلتونین نامیده می شود.

                          یا

                          هر نمودار متصل که حاوی مدار همیلتونی باشد به عنوان نمودار همیلتونی خوانده می شود.

                          همچنین بخوانید- نمودار اولر

                          مثال نمودار همیلتونی-

                          نمودار زیر مثالی از نمودار همیلتونی است-

                          اینجا،

                          • این نمودار شامل یک پیاده روی بسته ABCDEFA است.
                          • از هر راس نمودار دقیقاً یک بار بازدید می کند به جز راس شروع.
                          • در طول راه رفتن لبه ها تکرار نمی شوند.
                          • بنابراین ، این نمودار همیلتونی است.

                          متناوباً ، یک مدار همیلتونین ABCDEFA در نمودار بالا وجود دارد ، بنابراین یک نمودار همیلتونین است.

                          مسیر هامیلتونی-

                          • اگر در نمودار متصل پیاده روی وجود داشته باشد که دقیقاً یک بار بدون تکرار لبه ها از هر رأس نمودار بازدید کند ، پس چنین پیاده روی به عنوان مسیر همیلتون خوانده می شود.

                          یا

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

                          توجه داشته باشید

                          در مسیر هامیلتونی ، تمام لبه ها ممکن است پوشانده شوند یا نشوند اما لبه ها نباید تکرار شوند.

                          مثالهای مسیر هامیلتونی-

                          نمونه هایی از مسیر همیلتون به شرح زیر است -

                          مدار همیلتونین-

                          مدار همیلتونین به چرخه همیلتونین نیز معروف است .

                          • اگر در نمودار متصل پیاده روی وجود داشته باشد که دقیقاً یک بار از هر راس نمودار بازدید کند (به جز راس شروع) بدون تکرار لبه ها و به راس شروع بازگردد ، بنابراین چنین پیاده روی به عنوان مدار همیلتون خوانده می شود.

                          یا

                          • اگر چرخه ای در نمودار متصل وجود داشته باشد که شامل تمام رئوس نمودار باشد ، آن چرخه به عنوان مدار همیلتون خوانده می شود.

                          یا

                          • یک مسیر همیلتونی که در همان راس شروع و ختم می شود ، مدار همیلتونین نامیده می شود.

                          یا

                          • مسیر بسته همیلتون به عنوان مدار همیلتون خوانده می شود.

                          مثالهای مدار همیلتونین -

                          نمونه هایی از مدار همیلتونین به شرح زیر است -

                          یادداشت های مهم-

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

                          همچنین نمودار - Planar را بخوانید

                          مشکلات عملی مبتنی بر گرافهای هامیلتون در نظریه گراف-

                          چالش ها و مسائل-

                          نمودارهای هامیلتونی کدامیک از موارد زیر است / هستند؟

                          راه حل ها-

                          آ)

                          این نمودار نه حاوی مسیر همیلتون است و نه حاوی مدار همیلتونین است.

                          از آنجا که نمودار حاوی مدار همیلتون نیست ، بنابراین نمودار همیلتونین نیست .

                          ب)

                          این نمودار نه حاوی مسیر همیلتون است و نه حاوی مدار همیلتونین است.

                          از آنجا که نمودار حاوی مدار همیلتون نیست ، بنابراین نمودار همیلتونین نیست .

                          ج)

                          نمودار هم شامل مسیر همیلتون (ABCDHGFE) و هم مدار همیلتون (ABCDHGFEA) است.

                          از آنجا که نمودار شامل یک مدار همیلتونین است ، بنابراین یک نمودار همیلتونین است .

                          د)

                          نمودار شامل هر دو مسیر همیلتون (ABCDEFG) و مدار همیلتون (ABCDEFGA) است.

                          از آنجا که نمودار شامل یک مدار همیلتونین است ، بنابراین یک نمودار همیلتونین است .

                          ه)

                          این نمودار نه حاوی مسیر همیلتون است و نه حاوی مدار همیلتونین است.

                          از آنجا که نمودار حاوی مدار همیلتون نیست ، بنابراین نمودار همیلتونین نیست .

                          و)

                          نمودار شامل هر دو مسیر همیلتون (ABCDEFGHI) و یک مدار همیلتونین (ABCDEFGHIA)

                          از آنجا که نمودار شامل یک مدار همیلتونین است ، بنابراین یک نمودار همیلتونین است .

                          برای درک بهتر در مورد نمودارهای همیلتونین در تئوری نمودار ،

                          این سخنرانی ویدئویی را مشاهده کنید

                          مقاله بعدی - نمودار دو طرفه

                          یادداشت های بیشتر و سایر مطالب مطالعه تئوری نمودار را دریافت کنید.

                          با مراجعه به کانال YouTube ما LearnVidFun ، سخنرانی های ویدیویی را تماشا کنید .

                          خلاصه

                          نمودار همیلتونین |  مسیر همیلتونین |  مدار همیلتونین

                          نام مقاله

                          نمودار همیلتونین | مسیر همیلتونین | مدار همیلتونین

                          شرح

                          نمودار Hamiltonian in Graph Theory- نمودار Hamiltonian یک نمودار متصل است که شامل یک مدار Hamiltonian است. مثالهای نمودار همیلتونی. مسیر Hamiltonian و Hamiltonian Circuit- مسیر Hamiltonian مسیری در یک نمودار متصل است که شامل همه رئوس نمودار است. یک مسیر همیلتونین بسته ، مدار همیلتونین نامیده می شود.

                          نویسنده

                          آکشی سینگال

                          نام ناشر

                          دروازه ویدیالی

                          https://www.gatevidyalay.com/hamiltonian-graphs-hamiltonian-path-hamiltonian-circuit/

                          چگونه شماره رنگی را پیدا کنیم | الگوریتم رنگ آمیزی نمودار


                          ما بحث کردیم

                          • Graph Coloring فرایندی است که رنگها را به رئوس یک نمودار اختصاص می دهد.
                          • این اطمینان حاصل می کند که هیچ دو راس مجاور نمودار با یک رنگ رنگی نیستند.
                          • Chromatic Number حداقل رنگ مورد نیاز برای رنگ آمیزی صحیح هر نمودار است.

                           

                          در این مقاله ، ما در مورد چگونگی پیدا کردن شماره Chromatic هر نمودار بحث خواهیم کرد.

                           

                           

                          الگوریتم رنگ آمیزی نمودار-

                           

                          • هیچ الگوریتمی کارآمد برای رنگ آمیزی نمودار با حداقل تعداد رنگ وجود ندارد.
                          • نمودار رنگ آمیزی یک مشکل کامل NP است.

                           

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

                           

                          الگوریتم حریص-

                           

                          مرحله 01:

                           

                          اولین راس را با اولین رنگ رنگ کنید.

                           

                          مرحله 02:

                           

                          اکنون ، رئوس باقی مانده (V-1) را یکی یکی در نظر بگیرید و موارد زیر را انجام دهید-

                           

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

                           

                          اشکال الگوریتم حریص-

                           

                          اشکال زیر الگوریتم حریصانه فوق وجود دارد -

                          • الگوریتم فوق همیشه از حداقل تعداد رنگ استفاده نمی کند.
                          • تعداد رنگهای استفاده شده گاهی به ترتیب پردازش رأس بستگی دارد.

                           

                          همچنین انواع نمودارها را در تئوری نمودار بخوانید

                           

                          مشكلات عملي بر اساس يافتن تعداد كروماتيك يك نمودار-

                           

                          مسئله -01:

                           

                          شماره رنگی نمودار زیر را پیدا کنید-

                           

                           

                           

                          راه حل-

                           

                          با استفاده از الگوریتم حریص ، ما باید-

                           

                          راسآبجدهf
                          رنگC1C2C1C2C1C2

                           

                          از اینجا،

                          • حداقل تعداد رنگهایی که برای رنگ آمیزی نمودار داده شده استفاده می شود 2 رنگ است.
                          • بنابراین ، Chromatic Number نمودار داده شده = 2.

                           

                          نمودار داده شده ممکن است به درستی با استفاده از 2 رنگ مطابق شکل زیر رنگ آمیزی شود -

                           

                           

                          مسئله 02:

                           

                          شماره رنگی نمودار زیر را پیدا کنید-

                           

                           

                          راه حل-

                           

                          با استفاده از الگوریتم حریص ، ما باید-

                           

                          راسآبجدهf
                          رنگC1C2C2C3C3C1

                           

                          از اینجا،

                          • حداقل تعداد رنگهایی که برای رنگ آمیزی نمودار داده شده استفاده می شود 3 است.
                          • بنابراین ، Chromatic Number نمودار داده شده = 3.

                           

                          نمودار داده شده ممکن است به درستی با استفاده از 3 رنگ مطابق شکل زیر رنگ آمیزی شود -

                           

                           

                          مسئله -03:

                           

                          شماره رنگی نمودار زیر را پیدا کنید-

                           

                           

                          راه حل-

                           

                          با استفاده از الگوریتم حریص ، ما باید-

                           

                          راسآبجدهfg
                          رنگC1C2C1C3C2C3C4

                           

                          از اینجا،

                          • حداقل تعداد رنگهایی که برای رنگ آمیزی نمودار داده شده استفاده می شود 4 است.
                          • بنابراین ، Chromatic Number نمودار داده شده = 4.

                           

                          نمودار داده شده ممکن است به درستی با استفاده از 4 رنگ مطابق شکل زیر رنگ آمیزی شود -

                           

                           

                          مشکل -04:

                           

                          شماره رنگی نمودار زیر را پیدا کنید-

                           

                           

                          راه حل-

                           

                          با استفاده از الگوریتم حریص ، ما باید-

                           

                          راسآبجدهf
                          رنگC1C2C3C1C2C3

                           

                          از اینجا،

                          • حداقل تعداد رنگهایی که برای رنگ آمیزی نمودار داده شده استفاده می شود 3 است.
                          • بنابراین ، Chromatic Number نمودار داده شده = 3.

                           

                          نمودار داده شده ممکن است به درستی با استفاده از 3 رنگ مطابق شکل زیر رنگ آمیزی شود -

                           

                           

                          مسئله -05:

                           

                          شماره رنگی نمودار زیر را پیدا کنید-

                           

                           

                          راه حل-

                           

                           

                          با استفاده از الگوریتم حریص ،

                          • حداقل تعداد رنگ های مورد نیاز برای رنگ آمیزی نمودار داده شده 3 است.
                          • بنابراین ، Chromatic Number نمودار داده شده = 3.

                           

                          نمودار داده شده ممکن است به درستی با استفاده از 3 رنگ مطابق شکل زیر رنگ آمیزی شود -

                           

                           https://www.gatevidyalay.com/graph-coloring-chromatic-number/

                          مسئله های عملی مبتنی بر راه رفتن در تئوری گراف -


                          مسئله های  عملی مبتنی بر راه رفتن در تئوری گراف -

                           

                          مسئله -01:

                           

                          نمودار زیر را در نظر بگیرید-

                           

                           

                          تصمیم بگیرید که کدام یک از توالی های رئوس زیر راه رفتن را تعیین می کند.

                          برای کسانی که پیاده روی هستند ، تصمیم بگیرید که این یک مدار است ، یک مسیر ، یک چرخه یا یک مسیر.

                          1. a ، b ، g ، f ، c ، b
                          2. b ، g ، f ، c ، b ، g ، a
                          3. c ، e ، f ، c
                          4. c ، e ، f ، c ، e
                          5. a ، b ، f ، a
                          6. f ، d ، e ، c ، b

                           

                          راه حل-

                           

                          1. دنباله
                          2. راه رفتن
                          3. چرخه
                          4. راه رفتن
                          5. پیاده روی نیست
                          6. مسیر

                           

                          مسئله 02:

                           

                          نمودار زیر را در نظر بگیرید-

                           

                           

                          دنباله های زیر راس ها را در نظر بگیرید و به س questionsالات زیر پاسخ دهید

                          1. x ، v ، y ، w ، v
                          2. x ، u ، x ، u ، x
                          3. x ، u ، v ، y ، x
                          4. x ، v ، y ، w ، v ، u ، x

                           

                          1. کدام یک از توالی های فوق الذکر پیاده روی کارگردانی هستند؟
                          2. طول پیاده روی های مستقیم چند است؟
                          3. کدام پیاده روی های مستقیم مسیرهای هدایت شده ای نیز هستند؟
                          4. کدام پیاده روی های مستقیم نیز چرخه های کارگردانی هستند؟

                           

                          راه حل-

                           

                          قسمت 01:

                           

                          • فقط (A) و (B) پیاده روی های مستقیم هستند.
                          • (C) یک پیاده روی مستقیم نیست زیرا هیچ قوسی از راس u به راس v وجود ندارد.
                          • (D) یک پیاده روی مستقیم نیست زیرا هیچ قوسی از راس v به راس u وجود ندارد.

                           

                          قسمت 02:

                           

                          طول هر دو مسیر (A) و (B) دارای طول = 4 هستند.

                           

                          قسمت 03:

                           

                          • نه (A) و نه (B) مسیرهای هدایت شده ای نیستند.
                          • این به این دلیل است که رئوس در هر دو تکرار می شوند.
                          • Vertex v در Walk (A) و vertex u در Walk (B) تکرار می شود.

                           

                          قسمت 04:

                           

                          • هیچ یک از آنها چرخه های کارگردانی نیستند.
                          • Walk (A) چرخه مستقیمی را نشان نمی دهد زیرا رئوس شروع و پایان آن یکسان نیستند.
                          • Walk (B) چرخه مستقیمی را نشان نمی دهد زیرا رئوس / لبه ها را تکرار می کند.

                           

                          مسئله -03:

                           

                          نمودار زیر را در نظر بگیرید-

                           

                           

                           

                          توالی های داده شده را مشاهده کنید و ماهیت پیاده روی را در هر مورد پیش بینی کنید -

                          1. v1e1v2e2v3e2v2
                          2. v4e7v1e1v2e2v3e3v4e4v5
                          3. v1e1v2e2v3e3v4e4v5
                          4. v1e1v2e2v3e3v4e7v1
                          5. v6e5v5e4v4e3v3e2v2e1v1e7v4e6v6

                           

                          راه حل-

                           

                          1. پیاده روی باز
                          2. دنباله (مسیر نیست زیرا vertex v4 تکرار می شود)
                          3. مسیر
                          4. چرخه
                          5. مدار (چرخه نیست زیرا vertex v4 تکرار می شود)

                           

                           

                           

                          اندازه گیری های نمودار: طول ، فاصله ، قطر ، گریز از مرکز ، شعاع ، مرکز


                          یک نمودار به عنوان مجموعه ای از نقاط شناخته می شود که به عنوان "Vertices" شناخته می شوند و خطی که به این نقاط می پیوندد به عنوان "Edges" شناخته می شود. مجموعه ای متشکل از جایی است که 'V' رئوس و 'E' لبه است. 

                           

                          رئوس: {A ، B ، C ، D ، E ، F} 
                          لبه ها: {{A ، B} ، {A ، D} ، {A ، E} ، {B ، C} ، {C ، E} ، {C ، F} ، {D ، E} ، {E ، F}} 

                          اندازه گیری نمودار(Graph Measurements): چند روش اندازه گیری نمودار موجود است: 

                          1. طول( Length ) - 
                          طول نمودار به عنوان تعداد لبه های موجود در نمودار تعریف می شود. 
                           

                          طول نمودار: 8
                          AB ، BC ، CD ، DE ، EF ، FA ، AC ، CE 

                          2. 
                          فاصله بین دو راس (
                          The distance between two Vertices)- فاصله بین دو رئوس در یک نمودار تعداد لبه ها در کوتاهترین یا حداقل مسیر است. بین دو لبه حداقل فاصله موجود را ایجاد می کند. بین دو راس می تواند بیش از یک مسیر کوتاه وجود داشته باشد. 

                           

                           

                           

                           

                           

                          کمترین فاصله بین 1 - 5  برابر2  است
                          1 → 2 → 5 است

                          3. قطر نمودار (Diameter of graph)- 
                          قطر نمودار حداکثر فاصله بین جفت رئوس است. همچنین می تواند به عنوان حداکثر فاصله بین جفت رأس ها تعریف شود. راه حل آن یافتن همه مسیرها و سپس یافتن حداکثر از همه است. 

                           

                           

                          قطر: 3 
                          BC → CF → FG  

                          4. شعاع نمودار(Radius of graph) - شعاع نمودار تنها در صورت داشتن قطر وجود دارد. کمترین فاصله بین یک راس تا سایر رئوس به عنوان شعاع نمودار G در نظر گرفته می شود. این به عنوان r (G) نشان داده می شود. 

                           

                           

                          شعاع: 2
                          
                          Radius: 2
                          All available minimum radius: 
                          BC → CF,
                          BC → CE,
                          BC → CD,
                          BC → CA
                          
                          حداقل شعاع موجود: 
                           BC → CF, BC → CE, BC → CD, BC → CA

                          5- مرکز نمودار(Centre of graph) - 


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

                           

                           

                           

                           

                           

                          مرکز: الف  

                          6. خارج از مرکز بودن نمودار( Eccentricity of graph ) - 
                          به عنوان حداکثر فاصله یک راس از راس دیگر تعریف شده است. حداکثر فاصله بین یک راس تا سایر رئوس به عنوان خارج از مرکز راس در نظر گرفته می شود. با e (V) نشان داده می شود. 

                           

                           

                          گریز از مرکز از: 
                          (A، A) = 0 
                          (A، B) = 1 
                          (A، C) = 2 
                          (A، D) = 1 
                          حداکثر مقدار 2 است ، بنابراین گریز از مرکز 2 است

                           

                           

                          منبع

                          https://www.geeksforgeeks.org/graph-measurements-length-distance-diameter-eccentricity-radius-center/