Solutio problematis ad geometriam situs pertinentis

by Leonhardus Eulerus

Leonhardus Eulerus

Solvtio problematis ad geometriam sitvs pertinentis

1736

editio: Commentarii academiae scientiarvm imperialis Petropolitanae. Tomvs VIII. Ad annvm MDCCXXXVI. Petropoli, typis academiae cǀɔǀɔccxʟɪ. P. 128—140.
fons: 1. Commentarii academiae scientiarvm imperialis Petropolitanae. Tomvs VIII. Ad annvm MDCCXXXVI. Petropoli, typis academiae cǀɔǀɔccxʟɪ. P. 128—140.

2. Фляйшнер Г. Эйлеровы графы и смежные вопросы. М.: Мир, 2002. 335 с.: ил. ISBN 5-03-003115-4 (рус.). ISBN 0-444-88395-9 (англ.).

3. Herbert Fleischner. Eulerian Graphs and Related Topics. Part 1, Volume 1. Amsterdam: North-Holland, 1990. ISBN 0-444-88395-9.

§. 1.

P

Raeter illam Geometriae partem, quae circa quantitates verſatur, et omni tempore ſummo ſtudio eſt exculta, alterius partis etiamnum admodum ignotae primus mentionem fecit Leibnitzius, quam Geometriam situs vocauit. Iſta pars ab ipſo in ſolo situ determinando, situsque proprietatibus eruendis occupata esse ſtatuitur; in quo negotio neque ad quantitates reſpiciendum, neque calculo quantitatum vrendum sit. Cuiusmodi autem problemata ad hanc situs Geometriam pertineant, et quali methodo in iis reſoluendis vti oporteat, non ſatis eſt definitum. Quamobrem, cum nuper problematis cuiusdam mentio esset facta, quod quidem ad geometriam pertinere videbatur, at ita erat comparatum, vt neque determinationem quantitatum requireret, neque ſolutionem calculi quantitatum ope admitteret, id ad geometriam situs referre haud dubitaui: praeſertim quod in eius ſolutione ſolus situs in considerationem veniat, calculus vero nullius prorſus sit vſus. Methodum ergo meam quam ad huius generis problemata ſoluenda inueni, tanquam ſpecimen Geometriae situs hic exponere conſtitui.

§. 2. Problema autem hoc, quod mihi ſatis notum esse perhibebatur, erat ſequens: Regiomonti in Borussia esse inſulam A ${\mathfrak {der}}$ ${\mathfrak {Kneiphof}}$ dictam, fluuiumque eam cingentem in duos diuidi ramos, quemadmodum ex figura [Figura 1.] videre licet: ramos vero huius fluuii ſeptem inſtructos esse pontibus, a, b, c, d, e, f, et g. Circa hos pontes iam iſta proponebatur quaeſtio, num quis curſum ita inſtituere queat, vt per singulos pontes ſemel et non plus quam ſemel transeat. Hocque fieri posse, mihi dictum eſt, alios negare alios dubitare; neminem vero affirmare. Ego ex hoc mihi ſequens maxime generale formaui problema; quaecunque sit fluuii figura et diſtributio in ramos, atque quicunque fuerit numerus pontium, inuenire, vtrum per singulos pontes ſemel tantum transiri queat, an vero ſecus?

§. 3. Quod quidem ad problema Regiomontanum de ſeptem pontibus attinet, id reſolui posset facienda perfecta enumeratione omnium curſuum, qui inſtitui possunt; ex his enim innoteſceret, num quis curſus ſatisfaceret, an vero nullus. Hic vero ſoluendi modus propter tantum combinationum numerum et nimis esset difficilis atque operoſus, et in aliis quaeſtionibus de multo pluribus pontibus ne quidem adhiberi posset. Hoc porro modo si operatio ad finem perducatur multa inueniuntur, quae non erant in quaeſtione; in quo procul dubio tantae difficultatis cauſa consiſtit. Quamobrem missa hac methodo, in aliam inquisiui, quae plus non largiatur, quam oſtendat, vtrum talis curſus inſtitui queat an ſecus; talem enim methodum multo simpliciorem fore ſum ſuspicatus.

§. 4. Innititur autem tota mea methodus idoneo modo singulos pontium transitus designandi, in quo vtor litteris maiusculis A, B, C, D singulis regionibus adſcriptis, quae flumine ſunt ſeparatae. Ita, si quis ex regione A in regionem B transmigrat per pontem a siue b, hunc transitum denoto litterus AB, quarum prior praebet regionem ex qua exierat viator, poſterior vero dat regionem in quam pontem transgressus peruenit. Si deinceps viator ex regione B abeat in regionem D per pontem f, hic transitus repraeſentabitur litteris BD; duos autem hos transitus ſuccessiue inſtitutos AB et BD denoto tantum tribus litteris ABD, quia media B designat tam regionem, in quam primo transitu peruenit, quam regionem ex qua altero transitu exit.

§. 5. Simili modo si viator ex regione D progrediatur in regionem C per pontem g, hos tres transitus ſuccessiue factos quatuor litteris ABDC denotabo. Ex his enim quatuor litteris ABDG intelligetur viatorem primo in regione A exiſtentem transiisse in regionem B, hinc esse progressum in regionem D, ex hacque vltra esse profectum in C: cum vero hae regiones fluuiis sint a ſe inuicem ſeparatae, necesse eſt vt viator tres pontes transierit. Sic transitus per quatuor pontes ſuccessiue inſtituti quinque litteris denotabuntur; et si viator trans quotcunque pontes eat, eius migratio per litterarum numerum, qui vnitate eſt maior quam numerus pontium, denotabitur. Quare transitus per ſeptem pontes ad designandum octo requirit litteras.

§. 6. In hoc designando modo non reſpicio, per quos pontes transitus sit factus, ſed si idem transitus ex vna regione in aliam per plures pontes fieri poteſt, perinde eſt per quemnam transeat, modo in designatam regionem perveniat. Ex quo intelligitur, si curſus per ſeptem figurae pontes ita inſtitui posset, vt per singulos ſemel ideoque per nullum bis transeatur; hunc curſum octo litteris repraeſentari posse, easque litteras ita esse debere dispositas, vt immediata litterarum A et B ſuccessio bis occurrat, quia ſunt duo pontes a et b has regiones A et B iungentes, simili modo ſuccessio litterarum A et C quoque debet bis occurrere in illa octo litterarum ſerie; deinde ſuccessio litterarum A et D ſemel occurret; similiterque ſuccessio litterarum B et D, itemque C et D ſemel occurrat necesse eſt.

§. 7. Quaeſtio ergo huc reducitur, vt ex quatuor litteris A, B, C et D ſeries octo litterarum formetur, in qua omnes illae ſuccessiones toties occurrant quoties eſt praeceptum. Antequam autem ad talem dispositionem opera adhibeatur, oſtendi conuenit, vtrum tali modo hae litterae disponi queant an non. Si enim demonſtrari poterit talem dispositionem omnino fieri non posse, inutilis erit omnis labor, qui ad hoc efficiendum locaretur. Quamobrem regulam inueſtigaui, cuius ope tam pro hac quaeſtione, quam pro omnibus similibus, facile discerni queat, num talis litterarum dispositio locum habere queat.

§. 8. Considero ad huiusmodi regulam inueniendam vnicam regionem A, in quam quotcuncue pontes a, b, c, d etc. conducant [Figura 2.]. Horum pontium contemplor primo unicum a, qui ad regionem A ducat; si nunc viator per hunc pontem transeat vel ante transitum esse debuit in regione A vel poſt transitum in A perueniet; quare in ſupra ſtabilito transitus designandi modo oportet vt littera A ſemel occurrat. Si tres pontes puta a, b, c in regionem A conducant, et viator per omnes tres transeat, tum in designatione eius migrationis littera A bis occurret, siue ex A initio curſum inſtituerit siue minus. Simili modo si quinque pontes in A conducant, in designatione transitus per eos omnes littera A ter occurrere debet. Atque si numerus pontium fuerit quicunque numerus impar, tum si is vnitate augeatur, eius dimidium dabit, quot vicibus littera A occurrere debeat.

§. 9. In caſu igitur pontium transeundorum Regiomontano [Figura 1.], quia in inſulam A quinque pontes deducunt a, b, c, d, e, necesse eſt, vt in designatione transitus per hos pontes littera A ter occurrat. Deinde littera B, quia in regionem B tres pontes conducunt, bis debet occurrere, similique modo littera D bis debet occurrere, atque etiam littera C bis. In ſerie ergo octo litterarum, quibus transitus per ſeptem pontes deberet designari, littera A ter adesse deberet, litterarum vero B, C, et D vnaquaeque bis; id quod in ſerie octo litterarum omnino fieri nequit. Ex quo perſpicuum eſt, per ſeptem pontes Regiomontanos talem transitum inſtitui non posse.

§. 10. Simili modo de omni alio caſu pontium si quidem numerus pontium, qui in quamque regionem conducit fuerit impar, indicari poteſt, an per singulos pontes transitus ſemel fieri queat. Si enim euenit, vt ſumma omnium vicium, quibus singulae litterae occurrere debent, aequalis sit numero omnium pontium vnitate aucto, tum talis transitus fieri poteſt; sin autem vt in noſtro exemplo accidit, ſumma omnium vicium maior fuerit numero pontium vnitate aucto, tum talis transitus nequaquam inſtitui poteſt. Regula autem quam dedi pro numero vicium A ex numero pontium in regionem A deducentium inueniendo aeque valet; siue omnes pontes ex vna regione B, vt in figura [Figura 2.] repraeſentatur, ducant, siue ex diuersis; tantum enim regionem A considero, et inquiro quot vicibus littera A occurrere debeat.

§. 11. Si autem numerus pontium, qui in regionem A conducunt, fuerit par, tum circa transitum per singulos notandum eſt, vtrum initio viator curſum ſuum ex regione A inſtituerit an non. Si enim duo pontes in A conducant, et viator ex A curſum inceperit, tum littera A bis occurrere debet, ſemel enim adesse debet ad designandum exitum ex A per alterum pontem, et ſemel quoque ad designandum reditum in A per alterum pontem. Sin autem viator ex alia regione curſum inceperit, tum ſemel tantum littera A occurret, ſemel enim posita tam aduentum in A quam exitum inde denotabit, vt huiusmodi curſus designare ſtatui.

§. 12. Conducant iam quatuor pontes in regionem A, et viator ex A curſum incipiat, tum in designatione totius curſus littera A ter adesse debebit, si quidem per singulos ſemel transierit. At si ex alia regione ambulare inceperit, tum bis tantum littera A occurret. Si ſex pontes ad regionem A conducant, tum littera A, si ex A initium eundi eſt ſumtum, quater occurret, at si non ex A initio exierit viator, tum ter tantum occurrere debebit. Quare generaliter si numerus pontium fuerit par, tum eius dimidium dat numerum vicium, quibus littera A occurrere debet, si initium non eſt in regione A ſumtum; dimidium vero vnitate auctum dabit numerum vicium, quoties littera A occurrere debet, initio curſus in ipſa regione A ſumto.

§. 13. Quia autem in tali curſu nonnisi ex vna regione initium fieri poteſt, ideo ex numero pontium, qui in quamuis regionem deducunt, ita numerum vicium, quoties littera quamque regionem denotans occurrere debet, definio, vt ſumam numeri pontium vnitate aucti dimidium, si numerus pontium fuerit impar; ipsius vero numeri pontium medietatem, si fuerit par. Deinde si numerus omnium vicium adaequet numerum pontium vnitate auctum, tum transitus desideratus ſuccedit, at initium ex regione, in quam impar pontium numerus ducit, capi debet. Sin autem numerus omnium vicium fuerit vnitate minor, quam pontium numerus vnitate auctus, tum transitus ſuccedet incipiendo ex regione, in quam par pontium numerus ducit, quia hoc modo vicium numerus vnitate eſt augendus.

§. 14. Proposita ergo quacunque aquae pontiumque figura, ad inveſtigandum, num quis per singulos ſemel transire queat, ſequenti modo operationem inſtituo. Primo singulas regiones aqua a ſe inuicem diremtas litteris A, B, C etc. designo. Secundo ſumo omnium pontium numerum, eumque vnitate augeo, atque ſequenti operationi praefigo. Tertio singulis litteris A, B, C etc. sibi ſubſcriptis, cuilibet adſcribo numerum pontium ad eam regionem deducentium. Quarto eas litteras, quae pares adſcriptos habent numeros signo aſteriſco. Quinto singulorum horum numerorum parium dimidia adiicio, imparium vero vnitate auctorum dimidia ipsis adſcribo. Sexto hos numeros vltimo ſcriptos in vnam ſummam coniicio; quae ſumma, si vel vnitate minor fuerit vel aequalis numero ſupra praefixo, qui eſt numeros pontium vnitate auctus, tum concludo transitum desideratum perfici posset. Hoc vero eſt tenendum, si ſumma inuenta fuerit vnitate minor, quam numerus ſupra positus, tum initium ambulationis ex regione aſteriſtico notata fieri debere, contra vero ex regione non signata si ſumma fuerit aequalis numero praeſcripto. Ita ergo pro caſu Regiomontano operationem inſtituo, vt ſequitur:

Numerus pontium 7, habetur ergo 8.

${\scriptstyle {\mathsf {Pontes}}} \atop \left.{\begin{array}{cc}{\rm {{\mathsf {A,}}\quad {\mathsf {5}}\quad }}\\{\rm {{\mathsf {B,}}\quad {\mathsf {3}}\quad }}\\{\rm {{\mathsf {C,}}\quad {\mathsf {3}}\quad }}\\{\rm {{\mathsf {D,}}\quad {\mathsf {3}}\quad }}\\\end{array}}\right|\left.{\begin{array}{c}{\mathsf {3}}\\{\mathsf {2}}\\{\mathsf {2}}\\{\mathsf {2}}\\\end{array}}\right.$

Quia ergo plus prodiit quam 8, huiusmodi transitus nequaquam fieri poteſt.

§. 15. Sint duae inſulae A et B aqua circumdatae, quacum aqua communicent quatuor fluuii, quemadmodum figura [Figura 3.] repraeſentat. Traiecto porro sint ſuper aquam inſulas circumdantem et fluuios quindecim pontes a, b, c, d, etc. et quaeritur, num quis curſum ita inſtituere queat, vt per omnes pontes transeat, per nullum autem plus quam ſemel. Designo ergo primum omnes regiones, quae aqua a ſe inuicem ſunt ſeparatae litteris A, B, C, D, E, F cuiusmodi ergo ſunt ſex regiones. Dein numerum pontium 15 vnitate augeo, et ſummam 16 ſequenti operationi praefigo.

${\qquad \qquad \quad \;\;{\underline {\;{\mathsf {16}}\quad }} \atop \left.{\begin{array}{cc}{\rm {{\mathsf {A}}\scriptstyle {\text{✴}}\displaystyle \;\;^{{\underline {\displaystyle {\;\;\;}}}\;}{\mathsf {8}}\quad }}\\{\rm {{\mathsf {B}}\scriptstyle {\text{✴}}\displaystyle \;\;^{{\underline {\displaystyle {\;\;\;}}}\;}{\mathsf {4}}\quad }}\\{\rm {{\mathsf {C}}\scriptstyle {\text{✴}}\displaystyle \;\;^{{\underline {\displaystyle {\;\;\;}}}\;}{\mathsf {4}}\quad }}\\{\rm {{\mathsf {D}}^{{\underline {\displaystyle {\;\;\;\;\;\;}}}\;}{\mathsf {3}}\quad }}\\{\rm {{\mathsf {E\,}}^{{\underline {\displaystyle {\;\;\;\;\;\;}}}\;}{\mathsf {5}}\quad }}\\{\rm {{\mathsf {F}}\scriptstyle {\text{✴}}\displaystyle \;\;^{{\underline {\displaystyle {\;\;\;}}}\;}{\mathsf {6}}\quad }}\\\end{array}}\right|\left.{\begin{array}{r}{\mathsf {\;4}}\\{\mathsf {\;2}}\\{\mathsf {\;2}}\\{\mathsf {\;2}}\\{\mathsf {\;3}}\\{\mathsf {\;3}}\\\end{array}}\right.} \atop \qquad \qquad \quad \;\;{\overline {\;{\mathsf {16}}\quad }}$

Tertio litteras A, B, C etc. sibi inuicem ſubſcribo, et ad quamque numerum pontium, qui in eam regionem ducunt pono, vt ad A octo ducunt pontes, ad B quatuor etc. Quarto litteras, quae pares adiunctos habent numeros aſterico noto. Quinto in tertiam columnam ſcribo parium numerorum dimidia, impares vero vnitate augeo, et ſemisses appono. Sexto tertiae columnae numeros inuicem addo, et obtineo ſummam 16. quae cum aequalis sit numero ſupra posito 16, ſequitur transitum desiderato modo fieri posse, si modo curſus vel ex regione D vel E incipiatur, quippe quae non ſunt aſteriſco notatae. Curſus autem ita fieri poterit EaFbBcFdAeFfCgAhCiDkAmEnApBoElD vbi inter litteras maiusculas pontes simul colocaui, per quos fit transitus.

§. 16. Hac igitur ratione facile erit in caſu quam maxime composito iudicare, vtrum transitus per omnes pontes ſemel tantum fieri queat, an non. Hoc tamen adhuc multo faciliorem tradam modum idem dignoſcendi, qui ex hoc ipſo modo non difficulter eruetur, poſtquam ſequentes obſeruationes in medium protulero. Primo autem obſeruo omnes numeros pontium singulis litteris A, B, C etc. adſcriptos simul ſumptos duplo maiores esse toto pontium numero. Huius rei ratio eſt, quod in hoc computo, quo pontes omnes in datam regionem ducentes numerantur, quilibet pons bis numeretur; refertur enim quisque pons ad vtramque regionem, quas iungit.

§. 17. Sequitur ergo ex hac obſeruatione ſummam omnium pontium, qui in singulas regiones conducunt, esse numerum parem, quia eius dimidium pontium numero aequatur. Fieri ergo non poteſt, vt inter numeros pontium in quamlibet regionem ducentium vnicus sit impar; neque etiam vt tres sint impares, neque quinque, etc. Quare si qui pontium numeri litteris A, B, C, etc, adſcripti ſunt impares, necesse eſt vt eorum numerus sit par, ita in exemplo Regiomontano quatuor erant pontium numeri impares litteris regionum A, B, C, D adſcripti, vti ex §. 14. videre licet; atque in exemplo praecedente §. 15, duo tantum ſunt numeri impares, litteris D et E adſcripti.

§. 18. Cum ſumma omnium numerorum litteris A, B, C etc. adiunctorum aequet duplum pontium numerum, manifeſtum eſt illam ſummam binario auctam, et per 2 diuiſam dare numerum operationi praefixum. Si igitur omnes numeri litteris A, B, C, D etc. adſcripti fuerint pares, et eorum singulorum medietates capiantur ad numeros tertiae columnae obtinendos, erit horum numerorum ſumma vnitate minor, quam numerus praefixus. Quamobrem his casibus ſemper transitus per omnes pontes fieri poteſt. In quacunque enim regione curſus incipiatur, ea habebit pontes numero pares ad ſe conducentes, vti requiritur. Sic in exemplo Regiomontano fieri poteſt, vt quis per omnes pontes bis transgrediatur, quilibet enim pons, quasi in duos erit diuiſus, numerusque pontium in quamuis regionem ducentium erit par.

§. 19. Praieterea si duo tantum numeri litteris A, B, C etc. adſcripti fuerint impares, reliqui vero omnes pares, tum ſemper desideratus transitus ſuccedet, si modo curſus ex regione ad quam pontium impar numerus Tendit incipiatur. Si enim pares numeri biſecentur atque etiam impares vnitate aucti, vti praeceptum eſt, ſumma harum medietatum vnitate erit maior quam numerus pontium, ideoque aequalis ipsi numero praefixo. Ex hocque porro perſpicitur, si quatuor vel ſex vel octo etc. fuerint numeri impares in ſecunda columna, tum ſummam numerorum tertiae columnae maiorem fore numero praefixo, eumque excedere vel vnitate, vel binario vel ternario etc. et idcirco transitus fieri nequit.

§. 20. Caſu ergo quocunque proposito ſtatim facillime poterit cognoſci, vtrum transitus per omnes pontes ſemel inſtitui queat an non, ope huius regulae. Si fuerint plures duabus regiones, ad quas ducentium pontium numerus eſt impar, tum certo affirmari poteſt, talem transitum non dari. Si autem ad duas tantum regiones ducentium pontium numerus eſt impar, tunc transitus fieri poterit, si modo curſus in altera harum regionum incipiatur. Si denique nulla omnino fuerit regio, ad quam pontes numero impares conducant, tum transitus desiderato modo inſtitui poterit, in quacunque regione ambulandi initium ponatur. Hac igitur data regula problemati proposito plenissime ſatisfit.

§. 21. Quando autem inuentum fuerit talem transitum inſtitui posse, quaeſtio ſupereſt quomodo curſus sit dirigendus. Pro hoc ſequenti vtor regula; tollantur cogitatione quoties fieri poteſt, bini pontes, qui ex vna regione in aliam ducunt, quo pacto pontium numerus vehementer plerumque diminuetur, tum quaeratur, quod facile fiet, curſus desideratus per pontes reliquos, quo inuento pontes cogitatione ſublati hunc ipſum curſum non multum turbabunt, id quod paululum attendenti ſtatim patebit; neque opus esse iudico plura ad curſus reipſa formandos praecipere.