Séance 7 - postier chinois

[3]:
import networkx as nx
import numpy as np

# Create a connected graph with 12 nodes
G = nx.erdos_renyi_graph(
    12, 0.3
)  # Using a random graph for simplicity, adjust probability for connectivity

# Ensure the graph is connected, regenerate if not
while not nx.is_connected(G):
    G = nx.erdos_renyi_graph(12, 0.3)

# Get the adjacency matrix
adj_matrix = nx.adjacency_matrix(G)

# Convert to a dense numpy array for easier viewing
adj_matrix_dense = adj_matrix.todense()

print("Adjacency Matrix:")
print(adj_matrix_dense)
Adjacency Matrix:
[[0 1 0 1 0 0 0 0 1 1 1 0]
 [1 0 1 0 0 0 1 0 1 0 0 1]
 [0 1 0 0 1 0 0 1 0 1 1 0]
 [1 0 0 0 0 0 0 0 1 0 0 0]
 [0 0 1 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 1 1 1 0 0]
 [0 1 0 0 0 0 0 0 0 1 0 0]
 [0 0 1 0 0 1 0 0 1 1 1 1]
 [1 1 0 1 0 1 0 1 0 0 0 0]
 [1 0 1 0 0 1 1 1 0 0 0 0]
 [1 0 1 0 0 0 0 1 0 0 0 0]
 [0 1 0 0 0 0 0 1 0 0 0 0]]
[4]:
import matplotlib.pyplot as plt

# Draw the graph
pos = nx.spring_layout(G)  # positions for all nodes - seed for reproducibility
fig, ax = plt.subplots(figsize=(4, 4))
nx.draw(
    G,
    pos,
    with_labels=True,
    node_color="skyblue",
    node_size=700,
    edge_color="k",
    linewidths=1,
    font_size=15,
    ax=ax,
)

# Display the plot
plt.show()
../../../_images/practice_years_2025_seance7_postier_chinois_2_0.png
[5]:
def degre_noeuds(adj_matrix_dense):
    return adj_matrix_dense.sum(axis=1)


degre_noeuds(adj_matrix_dense)
[5]:
array([5, 5, 5, 2, 1, 3, 2, 6, 5, 5, 3, 2])
[6]:
def tous_noeuds_degre_impair_sauf_deux(adj_matrix_dense):
    deg = degre_noeuds(adj_matrix_dense)
    impairs = (deg % 2).sum()
    return bool(impairs <= 2)


tous_noeuds_degre_impair_sauf_deux(adj_matrix_dense)
[6]:
False
[7]:
def plus_court_chemin(adj_matrix, debut, fin):
    distance = np.array([np.inf for i in range(len(adj_matrix))])
    predecessors = np.array([-1 for i in range(len(adj_matrix))])
    distance[debut] = 0
    for t in range(len(adj_matrix)):
        for i in range(len(adj_matrix)):
            for j in range(len(adj_matrix)):
                d = distance[i] + adj_matrix[i, j]
                if adj_matrix[i, j] != 0 and distance[j] > d:
                    distance[j] = d
                    predecessors[j] = i
    chemin = []
    while fin != -1:
        chemin.append(int(fin))
        fin = predecessors[fin]
    return distance[fin], chemin[::-1]


plus_court_chemin(adj_matrix_dense, 0, 1)
[7]:
(np.float64(2.0), [0, 1])
[8]:
def appariement_approche(adj_matrix):
    degre = degre_noeuds(adj_matrix)
    impair = np.arange(degre.shape[0])[degre % 2 == 1]
    paires = []
    for i in impair:
        for j in impair:
            if i <= j:
                continue
            paires.append((i, j, plus_court_chemin(adj_matrix, i, j)[0]))
    paires.sort()
    appariement = []
    selectionne = set()
    for i, j, d in paires:
        if i not in selectionne and j not in selectionne:
            selectionne.add(i)
            selectionne.add(j)
            appariement.append((i, j))
    return appariement


appariement = appariement_approche(adj_matrix_dense)
appariement
[8]:
[(np.int64(1), np.int64(0)),
 (np.int64(4), np.int64(2)),
 (np.int64(8), np.int64(5)),
 (np.int64(10), np.int64(9))]
[9]:
def ajout_arc(adj_matrix):
    copie = adj_matrix.copy()
    appariement = appariement_approche(adj_matrix_dense)
    for i, j in appariement:
        chemin = plus_court_chemin(adj_matrix, i, j)[1]
        for k in range(len(chemin) - 1):
            copie[chemin[k], chemin[k + 1]] += 1
            copie[chemin[k + 1], chemin[k]] += 1
    return copie


matrice_paire = ajout_arc(adj_matrix_dense)
matrice_paire
[9]:
array([[0, 2, 0, 1, 0, 0, 0, 0, 1, 2, 2, 0],
       [2, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1],
       [0, 1, 0, 0, 2, 0, 0, 1, 0, 1, 1, 0],
       [1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
       [0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0, 1, 2, 1, 0, 0],
       [0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
       [0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 1],
       [1, 1, 0, 1, 0, 2, 0, 1, 0, 0, 0, 0],
       [2, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0],
       [2, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0],
       [0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0]])
[10]:
degre_noeuds(matrice_paire)
[10]:
array([8, 6, 6, 2, 2, 4, 2, 6, 6, 6, 4, 2])
[11]:
def chemin_passant_par_tous_les_arcs(matrice):
    """
    Retourne un chemin passant par tous les arcs d'un graphe non orienté,
    représenté par une matrice d'adjacence.
    Retourne None si le graphe n'est pas eulérien.
    """
    # Conversion matrice -> liste d'adjacence
    n = len(matrice)
    graphe = {}
    for i in range(n):
        for j in range(i + 1, n):
            if matrice[i][j] > 0:
                if i not in graphe:
                    graphe[i] = []
                if j not in graphe:
                    graphe[j] = []
                graphe[i].append(j)
                graphe[j].append(i)

    # Vérifie si le graphe est eulérien
    def est_eulerien(g):
        degres = [0] * n
        for u in g:
            degres[u] = len(g[u])
        degres_impairs = [u for u in range(n) if degres[u] % 2 != 0]
        if len(degres_impairs) == 0 or len(degres_impairs) == 2:
            return True, degres_impairs
        return False, degres_impairs

    # Algorithme de Hierholzer
    def hierholzer(g):
        stack = []
        chemin = []
        sommet_courant = 0
        stack.append(sommet_courant)

        while stack:
            u = stack[-1]
            if g[u]:
                v = g[u].pop()
                g[v].remove(u)  # Supprime l'arc dans les deux sens
                stack.append(v)
            else:
                chemin.append(stack.pop())
        return chemin[::-1]

    # Copie du graphe pour ne pas le modifier
    g = {}
    for u in graphe:
        g[u] = graphe[u].copy()

    chemin = hierholzer(g)
    return chemin


chemin_passant_par_tous_les_arcs(matrice_paire)
[11]:
[0, 10, 7, 11, 1, 8, 7, 9, 6, 1, 2, 9, 5, 7, 2, 4, 8, 3, 0, 1, 8, 9, 10]
[ ]:


Notebook on github