Commentarii Academiae Scientarum Imperialis Petropolitanae, 8 (1736), 128–140 + Plate VIII.
This famous paper on the bridges of Königsberg, in East Prussia, is generally considered to be the beginning of graph theory. In the original the three figures are printed on a separate plate, but in this Web version they have been moved into the text.
The town of Königsberg was taken over by Russia after the second world war and is now officially known as Kaliningrad.
{128}
Praeter illam Geometriae partem, quae circa quantititates versatur, et omni tempore summo studio est exculta, alterius partis etiamnum admodum ignotae primus mentionem fecit Leibnitzius, quam Geometriam situs vocauit. Ista pars ab ipso in solo, situ determinando, situsque proprietatibus eruendis occupata esse statuitur; in quo negotio neque ad quantitates respiciendum, neque calculo quantitatum vtendum sit. Cuiusmodi autem problemata ad hanc situs Geometriam pertineant, et quali methodo in iis resoluendis vti oporteat, non satis est 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 solutionem calculi quantitarum ope admitteret, id ad geometriam situs referre haud dubitaui: praesertim quod in eius solutione solus situs in considerationem veniat, calculus vero nullius prorsus sit vsus. Methodum ergo meam quam ad huius generis proble-{129}mata soluenda inueni, tanquam specimen Geometriae situs hic exponere constitui.
Figura 1 §. 2. Problema autem hoc, quod mihi satis notum esse perhibebatur, erat sequens: Regiomonti in Borussia esse insulam A der Kneiphof dictam, fluuiumque eam cingentem in duos diuidi ramos, quemadmodum ex figura videre licet: ramos vero huius fluuii septem instructos esse pontibus, a, b, c, d, e, f, et g. Circa hos pontes iam ista proponebatur quaestio, num quis cursum ita instituere queat, vt per singulos pontes semel et non plus quam semel transeat. Hocque fieri posse, mihi dictum est, alios negare alios dubitare; neminem vero affirmare. Ego ex hoc mihi sequens maxime generale formaui problema; quaecunque sit fluuii figura et distributio in ramos, atque quicunque fuerit numerus pontium, inuenire, vtrum per singulos pontes semel tantum transiri queat, an vero secus?
§. 3. Quod quidem ad problema Regiomontanum de septem pontibus attinet, id resolui posset facienda perfecta enumeratione omnium cursuum, qui institui possunt; ex his enim innotesceret, num quis cursus satisfaceret, an vero nullus. Hic vero soluendi modus propter tantum combinationum numerum et nimis esset difficilis atque operosus, et in aliis quaestionibus de multo pluribus pontibus ne quidem adhiberi posset. Hoc porro modo si operatio ad finem perducatur multa inueniuntur, quae non erant in quaestione; in quo procul dubio tantae difficultatis causa consistit [1]. Quamobrem missa hac methodo, in aliam inquisiui, quae plus non {130} largiatur, quam ostendat, vtrum talis cursus institui queat an secus; talem enim methodum multo simpliciorem fore sum suspicatus [2].
§. 4. Innititur autem tota mea methodus idoneo modo singulos pontium transitus designandi, in quo vtor litteris maiusculis A, B, C, D, singulis regionibus adscriptis, quae flumine sunt separatae. Ita si quis ex regione A in regionem B transmigrat per pontem a siue b, hunc transitum denoto litteris AB, quarum prior praebet regionem ex qua exierat viator, postierior vero dat regionem in quam pontem transgressus peruenit. Si deinceps viator ex regione B abeat in regionem D per pontem f, hic transitus repraesentabitur litteris BD; duos autem hos transitus successiue institutos 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 successiue factos quatuor litteris ABDC denotabo. Ex his enim quatuor litteris ABDGThus in original intelligetur viatorem prima in regione A existentem transiisse in regionem B, hinc esse progressum in regionem D, ex hacque vltra esse profectum in C: cum vero hae regiones fluuiis sint a se inuicem separatae, necesse est vt viator tres pontes transierit. Sic transitus per quatuor pontes successiue instituti quinque litteris denotabuntur; et si viator trans quotcunque pontes eat, eius migratio per litterarum numerum, qui vnitate est ma-{131}ior quam numerus pontium, denotabitur. Quare transitus per septem pontes ad designandum octo requirit litteras.
§. 6. In hoc designando modo non respicio, per quos pontes transitus sit factus, sed si idem transitus ex vna regione in aliam per plures pontes fieri potest, perinde est per quemnam transeat, modo in designatam regionem perueniat. Ex quo intelligitur, si cursus per septem figurae pontes ita institui posset, vt per singulos semel ideoque per nullum bis transeatur; hunc cursum octo litteris repraesentari posse, easque litteras ita esse debere dispositas, vt immediata litterarum A et B successio bis occurrat, quia sunt duo pontes a et b has regiones A et B iungentes, simili modo successio litterarum A et C quoque debet bis occurrere in illa octo litterarum serie; deinde successio litterarum A et D semel occurret; similiterque successio litterarum B et D, itemque C et D semel occurrat necesse est.
§. 7. Quaestio ergo huc reducitur, vt ex quatuor litteris A, B, C et D series octo litterarum formetur, in qua omnes illae successiones toties occurrant quoties est praeceptum. Antequam autem ad talem dispositionem opera adhibeatur, ostendi conuenit, vtrum tali modo hae litterae disponi queant an non. Si enim demonstrari poterit talem dispositionem omnino fieri non posse, inutilis erit omnis labor, qui ad hoc efficiendum locaretur. Quamobrem regulam inuestigaui, cuius ope tam pro hac quaestione, quam pro {132} omnibus similibus, facile discerni queat, num talis litterarum dispositio locum habere queat.
Figura 2 §. 8. Considero ad huiusmodi regulam inueniendam vnicam regionem A, in quam quotcunque pontes a, b, c, d etc. conducant. Horum pontium contemplor primo vnicum a, qui ad regionem A ducat; si nunc viator per hunc pontem transeat vel ante transitum esse debuit in regione A vel post transitum in A perueniet; quare in supra stabilito transitus designandi modo oportet vt littera A semel 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 cursum instituerit 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.
Figura 1 §. 9. In casu igitur pontium transeundorum Regiomontano, quia in insulam A quinque pontes deducunt a, b, c, d, e, necesse est, 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 serie ergo octo litterarum, quibus transitus per septem pontes deberet designari, littera A ter adesse deberet, litterarum vero {133} B, C, et D vnaquaeque bis; id quod in serie octo litterarum omnino fieri nequit. Ex quo perspicuum est, per septem pontes Regiomontanos talem transitum institui non posse.
§. 10. Simili modo de omni alio casu pontium si quidem numerus pontium, qui in quamque regionem conducit fuerit impar, iudicari potest, an per singulos pontes transitus semel fieri queat. Si enim euenit, vt summa omnium vicium, quibus singulae litterae occurrere debent, aequalis sit numero omnium pontium vnitate aucto, tum talis trasitus fieri potest; sin autem vt in nostro exemplo accidit, summa omnium vicium maior fuerit numero pontium vnitate aucto, tum talis transitus nequaquam institui potest. 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 repraesentitur, 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 est, vtrum initio viator cursum suum ex regione A instituerit an non. Si enim duo pontes in A conducant, et viator ex A cursum inceperit, tum littera A bis occurrere debet, semel enim adesse debet ad designandum exitum ex A per alterum pontem, et semel quoque ad designandum reditum {134} in A per alterum pontem. Sin autem viator ex alia regione cursum inceperit, tum semel tantum littera A occurret, semel enim posita tam aduentum in A quam exitum inde denotabit, vt huiusmodi cursus designare statui.
§. 12. Conducant iam quatuor pontes in regionem A, et viator ex A cursum incipiat, tum in designatione totius cursus littera A ter adesse debebit, si quidem per singulos semel transierit. At si ex alia regione ambulare inceperit, tum bis tantum littera A occurret. Si sex pontes ad regionem A conducant, tum littera A, si ex A initium eundi est sumtum, 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 est in regione A sumtum; dimidium vero vnitate auctum dabit numerum vicium, quoties littera A occurrere debet, initio cursus in ipsa regione A sumto.
§. 13. Quia autem in tali cursu nonnisi ex vna regione initium fieri potest [3], ideo ex numero pontium, qui in quamuis regionem deducunt, ita numerum vicium, quoties littera quamque regionem denotans occurrere debet, definio, vt sumam 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 succedit, at initium ex regione, in quam impar pontium {135} numerus ducit, capi debet. Sin autem numerus omnium vicium fuerit vnitate minor, quam pontium numerus vnitate auctus, tum transitus succedet incipiendo ex regione, in quam par pontium numerus ducit, quia hoc modo vicium numerus vnitate est augendus.
§. 14. Proposita ergo quacunque aquae pontiumque figura, ad inuestigandum, num quis per singulos semel transire queat, sequenti modo operationem instituo. Primo singulas regiones aqua a se inuicem diremtas litteris A, B, C etc. designo. Secundo sumo omnium pontium numerum, eumque vnitate augeo, atque sequenti operationi praefigo. Tertio singulis litteris A, B, C etc. sibi subscriptis, cuilibet adscribo numerum pontium ad eam regionem deducentium. Quarto eas litteras, quae pares adscriptos habent numeros signo asterisco. Quinto singulorum horum numerorum parium dimidia adiicio, imparium vero vnitate auctorum dimidia ipsis adscribo. Sexto hos numeros vltimo scriptos in vnam summam coniicio, quae summa, si vel vnitate minor fuerit vel aequalis numero supra praefixo, qui est numerus pontium vnitate auctus, tum concludo transitum desideratum perfici possetRead ‘posse’ ?. Hoc vero est tenendum, si summa inuenta fuerit vnitate minor, quam numerus supra positus, tum initium ambulationis ex regione asteristico notata fieri debere, contra vero ex regione non signata si summa fuerit aequalis numero praescripto. Ita ergo pro casu Regiomontano operationem instituo, ut sequitur: {136}
| Numerus pontium 7, | habetur ergo 8 |
| Pontes | |
| A, 5 | 3 |
| B, 3 | 2 |
| C, 3 | 2 |
| D, 3 | 2 |
Quia ergo plus prodiit quam 8, huiusmodi transitus nequaquam fieri potest.
Figura 3 §. 15. Sint duae insulae A et B aqua circumdatae, quacum aqua communicent quatuor fluuii, quemadmodum figura repraesentat. TraiectoRead ‘Traiecti’ ? porro sint super aquam insulas circumdantem et fluuios quindecim pontes a, b, c, d, etc. et quaeritur, num quis cursum ita instituere queat, vt per omnes pontes transeat, per nullum autem plus quam semel. Designo ergo primum omnes regiones, quae aqua a se inuicem sunt separatae litteris A, B, C, D, E, F cuiusmodi ergo sunt sex regiones. Dein numerum pontium 15 vnitate augeo, et summam 16 sequenti operationi praefigo.
| 16 | ||
| A* | –8 | 4 |
| B* | –4 | 2 |
| C* | –4 | 2 |
| D | —3 | 2 |
| E | —5 | 3 |
| F* | –6 | 3 |
| 16 |
{137} Tertio litteras A, B, C etc. sibi inuicem subscribo, et ad quamque numerum pontium, qui in eam regionem ducunt pono, ut ad A octo ducunt pontes, ad B quatuor etc. Quarto litteras, quae pares adiunctos habent numeros asterisco noto. Quinto in tertiam columnam scribo parium numerorum dimidia, impares vero vnitate augeo, et semisses appono. Sexto tertiae columnae numeros inuicem addo, et obtineo summam 16. quae cum aequalis sit numero supra posito 16, sequitur transitum desiderato modo fieri posse, si modo cursus vel ex regione D vel E incipiatur, quippe quae non sunt asterisco notatae. Cursus autem ita fieri poterit EaFbBcFdAeFfCgAhCiDkAmEnApBoElD vbi inter litteras maiusculas pontes simul collocaui, per quos sit transitus.
§. 16. Hac igitur ratione facile erit in casu quam maxime composito iudicare, vtrum transitus per omnes pontes semel tantum fieri queat, an non. Hoc tamen adhuc multo faciliorem tradam modum idem dignoscendi, qui ex hoc ipso modo non difficulter eruetur, postquam sequentes obseruationes in medium protulero. Primo autem obseruo omnes numeros pontium singulis litteris A, B, C adscriptos simul sumtos duplo maiores esse toto pontium numero. Huius rei ratio est, 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.
{138} §. 17. Sequitur ergo ex hac obseruatione summam omnium pontium, qui in singulas regiones conducunt, esse numerum parem, quia eius dimidium pontium numero aequatur. Fieri ergo non potest, 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, adscripti sunt impares, necesse est vt eorum numerus sit par, ita in exemplo Regiomontano quatuor erant pontium numeri impares litteris regionum A, B, C, D adscripti, vti ex §. 14. videre licet; atque in exemplo praecedente §. 15, duo tantum sunt numeri impares, litteris D et E adscripti.
§. 18. Cum summa omnium numerorum litteris A, B, C etc. adiunctorum aequet duplum pontium numerum, manifestum est illam summam binario auctam, et per 2 diuisam dare numerum operationi praefixum. Si igitur omnes numeri litteris A, B, C, D etc. adscripti fuerint pares, et eorum singulorum medietates capiantur ad numeros tertiae columnae obtinendos, erit horum numerorum summa vnitate minor, quam numerus praefixus. Quamobrem his casibus semper transitus per omnes pontes fieri potest. In quacunque enim regione cursus incipiatur, ea habebit pontes numero pares ad se conducentes, vti requiritur. Sic in exemplo Regiomontano fieri potest, vt quis per omnes pontes bis transgrediatur, quilibet enim pons, quasi in duos erit diuisus, numerusque pontium in quamuis regionem ducentium erit par.
{139} §. 19. Praeterea si duo tantum numeri litteris A, B, C etc. adscripti fuerint impares, reliqui vero omnes pares, tum semper desideratus transitus succedet, si modo cursus ex regione ad quam pontium impar numerus tendit incipiatur. Si enim pares numeri bisecentur atque etiam impares vnitate aucti vti praeceptum est, summa harum medietatum vnitate erit maior quam numerus pontium, ideoque aequalis ipsi numero praefixo. Ex hocque porro perspicitur, si quatuor vel sex vel octo etc. fuerint numeri impares in secunda columna, tum summam numerorum tertiae columnae maiorem fore numero praefixo, eumque excedere vel vnitate, vel binario vel ternario etc. et idcirco transitus fieri nequit.
§. 20. Casu ergo quocunque proposito statim facillime poterit cognosci, vtrum transitus per omnes pontes semel institui queat an non, ope huius regulae. Si fuerint plures duabus regiones, ad quas ducentium pontium numerus est impar, tum certo affirmari potest, talem transitum non dari. Si autem ad duas tantum regiones ducentium pontium numerus est impar, tunc transitus fieri poterit, si modo cursus in altera harum regionum incipiatur. Si denique nulla omnino fuerit regio, ad quam pontes numero impares conducant, tum transitus desiderato modo institui poterit, in quacunque regione ambulandi initium ponatur. Hac igitur data regula problemati proposito plenissime satisfit.
{140} §. 21. Quando autem inuentum fuerit talem transitum institui posse, quaestio superest quomodo cursus sit dirigendus. Pro hoc sequenti vtor regula; tollantur cogitatione quoties fieri potest, bini pontes, qui ex vna regione in aliam ducunt, quo pacto pontium numerus vehementer plerumque diminuetur, tum quaeratur, quod facile fiet, cursus desideratus per pontes reliquos, quo inuento pontes cogitatione sublati hunc ipsum cursum non multum turbabunt, id quod paululum attendenti statim patebit; neque opus esse iudico plura ad cursus reipsa formandos praecipere.
