import networkx as nx
import itertools as it
from collections import defaultdict

G = nx.read_adjlist("graf.adjlist")

nx.draw_circular(G, with_labels=True, node_color="yellow", edgecolors="black")

Neko najveće sparivanje u grafu G

nx.max_weight_matching(G,maxcardinality=True)

{('b', 'h'), ('c', 'g'), ('e', 'f'), ('k', 'a')}

Funkcija koja vraća sva maksimalna sparivanja sa zadanim brojem bridova

def all_maximal_matching(G, number):
    max_matching = []
    for x in it.combinations(G.edges(), number):
        if nx.is_matching(G, set(x)):
            if nx.is_maximal_matching(G,set(x)):
                max_matching.append(set(x))
    print("Ukupno: ", len(max_matching))
    return max_matching

Sva maksimalna sparivanja s tri brida u grafu G

all_maximal_matching(G, 3)

Ukupno:  19

[{('a', 'c'), ('b', 'd'), ('k', 'e')},
 {('a', 'c'), ('b', 'd'), ('e', 'g')},
 {('a', 'c'), ('b', 'd'), ('e', 'f')},
 {('a', 'c'), ('b', 'h'), ('e', 'g')},
 {('a', 'b'), ('c', 'e'), ('d', 'g')},
 {('a', 'b'), ('c', 'h'), ('e', 'g')},
 {('a', 'b'), ('c', 'k'), ('e', 'g')},
 {('a', 'b'), ('c', 'g'), ('k', 'e')},
 {('a', 'b'), ('c', 'g'), ('e', 'f')},
 {('a', 'd'), ('b', 'h'), ('c', 'e')},
 {('a', 'd'), ('c', 'h'), ('k', 'e')},
 {('a', 'd'), ('c', 'h'), ('e', 'g')},
 {('a', 'd'), ('c', 'h'), ('e', 'f')},
 {('a', 'k'), ('b', 'd'), ('c', 'e')},
 {('a', 'k'), ('b', 'h'), ('e', 'g')},
 {('b', 'd'), ('c', 'h'), ('k', 'e')},
 {('b', 'd'), ('c', 'k'), ('e', 'g')},
 {('b', 'd'), ('c', 'k'), ('e', 'f')},
 {('b', 'd'), ('c', 'g'), ('k', 'e')}]

Sva najveća sparivanja u grafu G

all_maximal_matching(G, 4)

Ukupno:  17

[{('a', 'c'), ('b', 'h'), ('d', 'g'), ('k', 'e')},
 {('a', 'c'), ('b', 'h'), ('d', 'g'), ('e', 'f')},
 {('a', 'b'), ('c', 'h'), ('d', 'g'), ('k', 'e')},
 {('a', 'b'), ('c', 'h'), ('d', 'g'), ('e', 'f')},
 {('a', 'b'), ('c', 'k'), ('d', 'g'), ('e', 'f')},
 {('a', 'd'), ('b', 'h'), ('c', 'k'), ('e', 'g')},
 {('a', 'd'), ('b', 'h'), ('c', 'k'), ('e', 'f')},
 {('a', 'd'), ('b', 'h'), ('c', 'g'), ('k', 'e')},
 {('a', 'd'), ('b', 'h'), ('c', 'g'), ('e', 'f')},
 {('a', 'k'), ('b', 'h'), ('c', 'e'), ('d', 'g')},
 {('a', 'k'), ('b', 'd'), ('c', 'h'), ('e', 'g')},
 {('a', 'k'), ('b', 'd'), ('c', 'h'), ('e', 'f')},
 {('a', 'k'), ('c', 'h'), ('d', 'g'), ('e', 'f')},
 {('a', 'k'), ('b', 'd'), ('c', 'g'), ('e', 'f')},
 {('a', 'k'), ('b', 'h'), ('c', 'g'), ('e', 'f')},
 {('a', 'k'), ('b', 'h'), ('d', 'g'), ('e', 'f')},
 {('b', 'h'), ('c', 'k'), ('d', 'g'), ('e', 'f')}]

Jedno pohlepno bojanje vrhova grafa G

bojeV = nx.greedy_color(G, strategy="DSATUR")
bojeV

{'c': 0, 'a': 1, 'k': 2, 'e': 1, 'g': 2, 'd': 0, 'b': 2, 'h': 1, 'f': 0}

Funkcija koja daje particiju vrhova s obzirom na pohlepno bojanje

def pohlepna_particija(bojanje):
    particija = defaultdict(list)
    for key,value in bojanje.items():
        particija[value].append(key)
    return dict(particija)

pohlepna_particija(bojeV)

{0: ['c', 'd', 'f'], 1: ['a', 'e', 'h'], 2: ['k', 'g', 'b']}

Jedno pohlepno bojanje bridova grafa

nx.draw_circular(nx.line_graph(G), with_labels=True, node_color="yellow", edgecolors="black", node_size=1200)

bojeB = nx.greedy_color(nx.line_graph(G), strategy="DSATUR")
bojeB

{('a', 'c'): 0,
 ('c', 'e'): 1,
 ('c', 'g'): 2,
 ('c', 'k'): 3,
 ('c', 'h'): 4,
 ('e', 'g'): 0,
 ('e', 'k'): 2,
 ('a', 'k'): 1,
 ('e', 'f'): 3,
 ('a', 'b'): 2,
 ('a', 'd'): 3,
 ('d', 'g'): 1,
 ('b', 'd'): 0,
 ('b', 'h'): 1}

pohlepna_particija(bojeB)

{0: [('a', 'c'), ('e', 'g'), ('b', 'd')],
 1: [('c', 'e'), ('a', 'k'), ('d', 'g'), ('b', 'h')],
 2: [('c', 'g'), ('e', 'k'), ('a', 'b')],
 3: [('c', 'k'), ('e', 'f'), ('a', 'd')],
 4: [('c', 'h')]}

G.degree()

DegreeView({'a': 4, 'c': 5, 'b': 3, 'd': 3, 'k': 3, 'h': 2, 'e': 4, 'g': 3, 'f': 1})

Obojani vrhovi na slici

BOJE = {0:'#25bbf7', 1:'#5ac38d', 2:'#e8527c', 3:'#fdab8a', 4:'#7001a5'}
boje_vrhova = list(map(lambda u: BOJE[bojeV[u]], G.nodes()))
nx.draw_circular(G, with_labels=True, node_color=boje_vrhova, edgecolors="black")

Obojani bridovi na slici

for e in G.edges():
    if not(e in bojeB.keys()):
        e = (e[1], e[0])
    nx.set_edge_attributes(G, {e: {"color": BOJE[bojeB[e]]}})
nx.draw_circular(G, with_labels=True, node_color='yellow', edgecolors="black", edge_color=nx.get_edge_attributes(G,'color').values(), width=2)