WikiDer > ENG ZO'R teorema

BEST theorem

Yilda grafik nazariyasi, qismi diskret matematika, ENG ZO'R teorema soni uchun mahsulot formulasini beradi Evler davrlari yilda yo'naltirilgan (yo'naltirilgan) grafikalar. Ism uni kashf etgan odamlar ismlarining qisqartmasi: de Bruijn, van Aardenne-Ehrenfest, Smit va Tutte.

Aniq bayonot

Ruxsat bering G = (V, E) yo'naltirilgan grafik bo'lishi. Evleriya davri - bu har bir chetga aniq bir marta tashrif buyuradigan yo'naltirilgan yopiq yo'l. 1736 yilda, Eyler buni ko'rsatdi G agar shunday bo'lsa, faqat Eulerian sxemasiga ega G bu ulangan va daraja ga teng ustunlik har bir tepada. Ushbu holatda G Evleriya deb ataladi. Biz vertexning notekisligini belgilaymiz v deg tomonidan (v).

BEST teoremasida ec (G) bog'langan Euleriya grafigidagi Eulerian sxemalarining G formula bilan berilgan

Bu yerda tw(G) ning soni daraxtzorlar, qaysiki daraxtlar sobit vertikada ildiz tomon yo'naltirilgan w yilda G. Raqam tw(G) sifatida hisoblash mumkin aniqlovchi, versiyasi bo'yicha matritsa daraxti teoremasi yo'naltirilgan grafikalar uchun. Bu Evleriya grafikalarining o'ziga xos xususiyati tv(G) = tw(G) har ikki tepalik uchun v va w bog'langan Evler grafikasida G.

Ilovalar

BEST teoremasi shuni ko'rsatadiki, yo'naltirilgan grafikalardagi Evleriya davrlari sonini hisoblash mumkin polinom vaqti, muammo # P tugadi yo'naltirilmagan grafikalar uchun.[1] Shuningdek, u Eulerian zanjirlarini asimptotik hisoblashda ishlatiladi to'liq va to'liq ikki tomonlama grafikalar.[2][3]

Tarix

BEST teoremasi birinchi bo'lib van Aardenne-Erenfest va de Bryuyn (1951) ning ishlariga "dalil sifatida qo'shilgan yozuv" da ushbu shaklda bayon qilingan. Asl dalil shu edi ikki tomonlama va umumlashtirildi de Bruijn ketma-ketliklari. Bu Smit va Tutte (1941) tomonidan ilgari olingan natijaning o'zgarishi.

Izohlar

  1. ^ Brightwell va Vinkler, "Eulerian davrlarini hisoblash to'g'risida eslatma", CDAM tadqiqotlari bo'yicha hisobot LSE-CDAM-2004-12, 2004.
  2. ^ Brendan MakKey va Robert V. Robinson, To'liq grafada eulerian zanjirlarini asimptotik hisoblash, Kombinatorika, 10 (1995), yo'q. 4, 367-377.
  3. ^ M.I. Isaev, To'liq bipartitli grafikalardagi Evler davrlarining asimptotik soni Arxivlandi 2010-04-15 da Orqaga qaytish mashinasi (ichida.) Ruscha), Proc. 52-MFTI konferentsiyasi (2009), Moskva.

Adabiyotlar

  • Eyler, L. (1736), "Geometriam sittin pertinentis muammolarini hal qilish", Commentarii Academiae Scientiarum Petropolitanae (lotin tilida), 8: 128–140.
  • Tutte, V. T.; Smit, C. A. B. (1941), "4-darajali tarmoqdagi bir martalik yo'llarda", Amerika matematik oyligi, 48: 233–237, doi:10.2307/2302716, JSTOR 2302716.
  • van Aardenne-Erenfest, T.; de Bryuyn, N. G. (1951), "Yo'naltirilgan chiziqli grafikalardagi sxemalar va daraxtlar", Simon Stevin, 28: 203–217.
  • Tutte, V. T. (1984), Grafika nazariyasi, Reading, Mass.: Addison-Uesli.
  • Stenli, Richard P. (1999), Sanab chiquvchi kombinatoriyalar, Jild 2, Kembrij universiteti matbuoti, ISBN 0-521-56069-1.
  • Aigner, Martin (2007), Hisoblash kursi, Matematikadan magistrlik matnlari, 238, Springer, ISBN 3-540-39032-4.