Ejemplo 10.2.1 Notación para caminos
a. En el grafo que se muestra a continuación, la notación e1e2e4e3, se refiere claramente al camino siguiente: 1e1 2e2 3e4 3e3 2. Por otro lado, la notación e1 es ambigua si se utiliza para referirse a un camino. Podría significar 1e1 2 o 2e1 1.
1 2
3
e2
e3
e1 e4
b. En el grafo del inciso a), la notación 2 3 es ambigua, si se utiliza para referirse a un camino. Podría significar 2e2 3 o 2e3 3. Por otra parte, en el grafo siguiente, la notación 1 2 2 3 se refiere claramente al camino 1e1 2e2 2e3 3.
1 2 3
e2
e1 e3
Observe que si una gráfica G no tiene ningunas aristas paralelas, entonces cualquier camino en G está únicamente determinado por su sucesión de vértices.
Ejemplo 10.2.2 Caminos, senderos, trayectorias y circuitos
En el grafo siguiente, determine cuáles de los siguientes caminos son senderos, trayectorias, circuitos o circuitos simples.
a. v1e1v2e3v3e4v3e5v4 b. e1e3e5e5e6 c. v2v3v4v5v3v6v2
d. v2v3v4v5v6v2 e. v1e1v2e1v1 f. v1
1 2
6
3
4
5
e2
e5
e9
e4
e3
e7
e8
e10
e6
e1