C. Euler

Leonhard Euler (1707-1783) a fost un matematician elvețian care a pus bazele teoriei grafurilor. În celebra problemă a podurilor din Königsberg Euler a reușit să demonstreze că pentu configurația de poduri existente peste râul Pregel nu există un traseu conform căruia un om să treacă peste fiecare pod exact o dată. Modelul matematic folosit de Euler a fost primul graf desenat. Dacă problema avea soluție, atunci graful s-ar fi putut desena cu ajutorul unui instrument de scris, fără ca vârful acestuia să fie ridicat de pe hârtie.

În desenul alăturat toate punctele numerotate reprezintă extremități de muchii orizontale, verticale sau oblice. Toate muchiile desenate orizontal, vertical sau oblic incidente care sunt unul în prelungirea celuilalt sunt coliniare. Muchia este un segment de linie dreaptă care unește direct două puncte. De exemplu pe desenul nostru următoarele perechi de puncte reprezintă muchii: (2,5), (3,6), (9,14) sau (8,9). Următoarele perechi de puncte nu reprezintă muchii: (3,5), (3,11) sau (12,4).  

Un lanț simplu este o succesiune de muchii incidente pe care le putem desena pe hârtie fără să ridicăm vârful creionului și fără să trecem peste o muchie de mai multe ori. De exemplu (2, 3, 6, 7, 8, 9, 4) reprezintă un lanț simplu.

Un lanț simplificat este un lanț simplu în care se elimină toate punctele din interior pentru care cele două muchii în cauză sunt coliniare. Lanțul simplificat corespunzător exemplului de mai sus este (2,6,9,4). Cu alte cuvinte, într-un lanț simplificat se schimbă direcția în fiecare punct al lanțului, cu excepția ultimului punct.    

Un lanț simplificat este eulerian dacă trece prin fiecare muchie a grafului exact o dată.

Pentru desenul alăturat determinați lungimea minimă respectiv lungimea maximă a unui lanț eulerian simplificat și dați câte un exemplu.

Lungimea unui lanț simplificat este numărul de segmente din care este format lanțul. Muchiile coliniare consecutive aparțin aceluiași segment. De exemplu lanțul (2, 3, 6, 7, 8, 9, 4) NU este lanț simplificat. Lanțul simplificat corespunzător este (2, 6, 9, 4) și are lungimea 3, format din segmentele (2,6) (6,9) (9,4).

Sursa: problema originală (Zoltan Szabo)

Mai multe informații: https://ro.wikipedia.org/wiki/Leonhard_Euler, https://ro.wikipedia.org/wiki/Problema_podurilor_din_K%C3%B6nigsberg

 

C. Euler

Leonhard Euler (1707-1783) was a Swiss mathematician who laid the foundation of graph theory. In the famous Königsberg bridge problem, Euler showed that for the existing bridge configuration over the Pregel River there is no route for a man to cross each bridge exactly once. The mathematical model used by Euler was the first drawn graph. If the problem was solved, then the graph could have been drawn using a writing tool, without its tip being lifted off the paper.

In the given drawing all the numbered points represent extremes of horizontal, vertical or oblique edges. All the edges drawn horizontally, vertically or obliquely incidents that are one in extension of the other are collinear. The edge is a straight line segment that directly connects two points. For example, in our drawing the following pairs of points represent the edges: (2.5), (3.6), (9.14) or (8.9). The following pairs of points do not represent the edges: (3,5), (3,11) or (12,4).

A simple chain is a succession of incidental edges that we can draw on paper without raising the tip of the pencil and without crossing an edge several times. For example (2, 3, 6, 7, 8, 9, 4) is a simple chain.

A simplified chain is a simple chain in which all the interior points for which the two edges in question that are collinear are eliminated. The simplified chain corresponding to the example above is (2,6,9,4). In other words, in a simplified chain the direction at each point of the chain, except the last point, changes.

A simplified chain is eulerian if it passes through each edge of the graph exactly once.

For the given drawing, determine the minimum length or maximum length of a simplified Eulerian chain and give an example.

The length of a simplified chain is the number of segments from which the chain is formed. The consecutive collinear edges belong to the same segment. For example the chain (2, 3, 6, 7, 8, 9, 4) is NOT a simplified chain. The corresponding simplified chain is (2, 6, 9, 4) and has the length 3, consisting of segments (2,6) (6,9) (9,4).

Source: original problem (Zoltan Szabo)

More information: https://en.wikipedia.org/wiki/Leonhard_Euler, https://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg

Vezi comentarii
Logheaza-te in site pentru a trimite solutii si comentarii
bjh

1. Nu pare clar de ce (2, 4) nu este muchie.

2. Nu se defineste lungimea si este un pic neclar.

  - este numarul de muchii (cu sau fara simplificare) dintr-o cale? Ex: lungimea lui (2, 5) este 1, iar lungimea lui (2, 3, 6, 7, 8, 9, 4) este 6

  - sau este suma etichetelor (greutatilor) alocate fiecarui punct? Ex: lungimea lui (2, 5) este 7, iar lungimea lui (2, 3, 6, 7, 8, 9, 4) este 39

Deoarece nu se specifica faptul ca valorile nodurilor sint altceva decit simpla numerotare, as zice ca probabil prima varianta este cea considerata aici.


szabozoltan

LA exemple ce nu formeaza muchie, în loc de (2,4) trebuie scris (12,4).


ruxandra

Am corectat acum in enuntul problemei, multumesc!


ruxandra

Am primit si postat si definitia lungimii si un exemplu, ca sa nu mai fie neclaritati. 


bjh

Multumesc pentru confirmarea definitiei lungimii.

Definitia de lant simplificat era deja clara. Intrebarea mea era relativ la definitia lungimii, specificind "cu sau fara simplificare", iar exemplele date se refereau exclusiv la lungime.