نمودار خط

یک نمودار خط (همچنین به عنوان یک مجاورت ، پوشش ، مشتق ، مشتق ، لبه ، لبه به آرتکس دوگانه ، تبادل ، نماینده یا نمودا ر-obrazom) یک نمودار ساده با اتصال یک راس با هر لبه از آن بدست می آید. نمودار و اتصال دو راس با یک لبه IFF لبه های مربوطه دارای یک راس مشترک هستند (گروس و Yellen 2006 ، ص 20).

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

نمودارهای خط به زبان Wolfram به عنوان اجرا می شوندچگالی[G]شناسایی نمودار خط پیش ساخته بسیاری از نمودارهای نامگذاری شده را می توان با استفاده از زبان Wolfram به دست آوردگرافیک[نمودار ،"Linegraphname"].

تعداد نمودارهای خط ساده روی ، 2 ،. رئوس ها 1 ، 2 ، 4 ، 10 ، 24 ، 63 ، 166 ، 471 ، 1408 ،.(OEIS A132220) ، و تعداد نمودارهای خط ساده متصل 1 ، 1 ، 2 ، 5 ، 12 ، 30 ، 79 ، 227 ،.(OEIS A003089).

جدول زیر برخی از نمودارهای نامگذاری شده و نمودارهای مربوط به خط آنها را خلاصه می کند.

نمودارهای خط بدون پنجه هستند.

نمودار خط یک نمودار با گره ها ، لبه ها و درجه های راس حاوی گره ها و

لبه ها (Skiena 1990 ، ص 137). ماتریس بروز یک نمودار و ماتریس مجاور نمودار خط آن توسط

ماتریس هویت کجاست (Skiena 1990 ، ص 136).

کراوز (1943) ثابت کرد که یک راه حل برای یک نمودار ساده وجود دارد که IFF با هر راس ظاهر شدن در حداکثر دو عضو تجزیه ، به زیرگرافهای کامل تجزیه می شود. این قضیه ، با این حال ، برای اجرای یک الگوریتم کارآمد به دلیل تعداد زیادی از تجزیه های درگیر مفید نیست (غرب 2000 ، ص 280).

ون روویج و ویلف (1965) نشان می دهند که راه حلی برای یک نمودار ساده IFF وجود دارد بدون پنجه و نمودار الماس ناشی از دو مثلث عجیب و غریب است. در اینجا گفته می شود که یک زیرگراف مثلثی حتی اگر محله و ورتکس در تعداد عجیب و غریب برای برخی از نقاط قرار بگیرند و حتی اگر و در تعداد یکنواخت برای هر یک از نقاط قرار بگیرند (غرب 2000 ، ص 281).

یک نمودار ساده یک نمودار خط از برخی از نمودارهای ساده است اگر حاوی هیچ یک از نه نمودارهای فوق به عنوان یک زیرگراف ناشی از ممنوعه نباشد (ون روویج و ویلف 1965 ؛ بیینکه 1968 ؛ اسکینا 1990 ، ص 138 ؛ هاراری 1994 ، ص. 74-75 ؛ غرب 2000 ، ص 282 ؛ گروس و یلن 2006 ، ص 405). این بیانیه گاهی به عنوان قضیه Beineke شناخته می شود. این نه نمودار به زبان Wolfram به عنوان پیاده سازی شده استگرافیک["Beineke"]. از این نه ، یکی چهار گره (نمودار پنجه = نمودار ستاره = نمودار کامل دو طرفه) ، دو دارای پنج گره و شش دارای شش گره (از جمله نمودار چرخ) است.

نمودار با حداقل درجه راس حداقل 5 یک نمودار خط است اگر هیچ یک از شش نمودار Metelsky فوق به عنوان یک زیرگراف ناشی از آن وجود ندارد (Metelsky and Tyshkevich 1997). این شش نمودار به زبان Wolfram به عنوان اجرا شده استگرافیک["متلسکی"].

اگر کوچکترین عنصر طیف نمودار آن کمتر از (ون میگم ، 2010 ، لیو و همکاران 2010) یک نمودار خط نیست.

ویتنی (1932) نشان داد که به استثنای و هر دو نمودار متصل با نمودارهای خط ایزومورفیک ایزومورفیک هستند (Skiena 1990 ، ص 138).

Lehot (1974) یک الگوریتم زمان خطی را ارائه داد که نمودار اصلی را از نمودار خط خود بازسازی می کند. لیو و همکاران.(2010) الگوریتمی را برای بازسازی نمودار اصلی از نمودار خط خود ، که تعداد راس های موجود در نمودار خط است ، ارائه دهید. این الگوریتم نسبت به الگوریتم کارآمد روسوپولوس (1973) کارآمدتر است.

نمودار خط یک نمودار اویلری هر دو اویلری و همیلتون است (Skiena 1990 ، ص 138). اطلاعات بیشتر در مورد چرخه نمودارهای خط توسط Harary and Nash-Williams (1965) و Chartrand (1968) ارائه شده است.

گرفتن نمودار خط دو بار نمودار اصلی را برمی گرداند مگر اینکه نمودار خط یک نمودار به خودی خود ایزومورفیک باشد. در حقیقت ، تنها نمودار متصل به نمودار خط آن ، نمودار چرخه ای برای آن است (Skiena 1990 ، ص 137). نمودارهای نمودار نمودارهای چرخه (به عنوان مثال ، ، و غیره) نیز از نمودارهای خط آنها ایزومورفیک هستند ، بنابراین نمودارهایی که از نمودارهای خط آنها ایزومورفیک هستند نمودارهای منظم درجه 2 هستند و تعداد کل نمودارهای ساده غیر ضروری متصل استاین که از خطوط خطوط آنها ایزومورفیک است ، با تعداد پارتیشن های تعداد راس آنها که دارای کوچکترین قسمت هستند ، داده شده است ، برای 2 ،. توسط 0 ، 0 ، 1 ، 1 ، 1 ، 2 ، 2 ، 3 ، 4 ، 5 ، 6 ، 9 ، 10 ، 13 ، 17 ،.(OEIS A026796) ، که چند مورد از آنها در بالا نشان داده شده است.

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

با Wolfram کاوش کنید | آلفا

چیزهای بیشتری برای امتحان کردن:

• نمودار خط
• (110110 پایه 2) / (11 پایه 2)
• دایره شعاع 2 با مرکز (0 ، -2)