Menemukan Jalur Semua Sisi pada Grafik

Saya mencoba mendapatkan jalur pada grafik yang mencakup semua sisi, dan hanya melintasinya sekali. Ini berarti hanya akan ada dua titik "akhir" - yang memiliki jumlah simpul terpasang ganjil. Titik akhir ini akan memiliki satu sisi penghubung, atau menjadi bagian dari satu lingkaran dan memiliki 3 koneksi.

Jadi dalam kasus sederhana di bawah ini saya perlu melintasi node dalam urutan ini 1-2-3-4-5 (atau 5-4-3-2-1):

Dalam kasus yang lebih rumit, jalurnya adalah 1-2-3-4-2 (atau 1-2-4-3-2):

Di bawah ini juga merupakan grafik yang valid, dengan 2 titik akhir: 1-2-4-3-2-5

Saya telah mencoba mencari nama algoritme untuk menyelesaikan ini, dan mengira itu adalah "Masalah Tukang Pos Tiongkok", tetapi menerapkannya berdasarkan kode di https://github.com/rkistner/chinese-postman/blob/master/postman.py tidak memberikan hasil yang saya harapkan .

Jalur Euler terlihat hampir seperti yang dibutuhkan, tetapi implementasi networkx hanya akan berfungsi untuk jaringan tertutup (loop).

Saya juga melihat Jalur Hamilton - dan mencoba algoritme networkx - tetapi jenis grafiknya tidak didukung.

Idealnya saya ingin menggunakan Python dan networkx untuk mengimplementasikan ini, dan mungkin ada solusi sederhana yang sudah menjadi bagian dari perpustakaan, tapi sepertinya saya tidak dapat menemukannya.