import networkx as nx
from IPython import display
from sage.graphs.graph_coloring import edge_coloring

G1 = nx.read_adjlist("G1.adjlist")
G2 = nx.read_adjlist("G2.adjlist")
G3 = nx.read_adjlist("G3.adjlist")

G1 = Graph(G1)
G2 = Graph(G2)
G3 = Graph(G3)

Graf $G_1$

kromatski broj

G1.chromatic_number()

4

bridno kromatski broj

edge_coloring(G1,value_only=True)

4

jedno bojanje vrhova s minimalnim brojem boja

boje1=G1.coloring(hex_colors=True)
boje1

{'#ff0000': ['a', 'd', 'e'],
 '#7fff00': ['c'],
 '#00ffff': ['b'],
 '#7f00ff': ['f']}

Graf $G_1$ nije kritični graf jer se npr. brisanjem brida {b,d} ne smanjuje kromatski broj.

G1.show(vertex_color=boje1)

jedno bojanje bridova s minimalnim brojem boja

G1.show(edge_colors=edge_coloring(G1,hex_colors=True))

Graf $G_2$

kromatski broj

G2.chromatic_number()

3

bridno kromatski broj

edge_coloring(G2,value_only=True)

5

jedno bojanje vrhova s minimalnim brojem boja

boje2=G2.coloring(hex_colors=True)
boje2

{'#ff0000': ['a', 'b', 'c'], '#00ff00': ['e'], '#0000ff': ['f', 'd']}

Graf $G_2$ nije kritični graf jer se npr. brisanjem brida {a,e} ne smanjuje kromatski broj.

G2.show(vertex_color=boje2)

jedno bojanje bridova s minimalnim brojem boja

G2.show(edge_colors=edge_coloring(G2,hex_colors=True))

Graf $G_3$

kromatski broj

G3.chromatic_number()

5

bridno kromatski broj

edge_coloring(G3,value_only=True)

6

jedno bojanje vrhova s minimalnim brojem boja

boje3=G3.coloring(hex_colors=True)
boje3

{'#ff0000': ['a', 'c'],
 '#cbff00': ['e', 'b'],
 '#00ff66': ['f'],
 '#0066ff': ['g'],
 '#cc00ff': ['d']}

posG3 = G3.layout(layout = "spring", save_pos = True)

posG3

{'a': [2.4343634046665414, 0.8262462172977196],
 'g': [2.0204740359968723, -0.19297483161115722],
 'd': [2.006927219580923, -0.9805398451986496],
 'c': [1.0, -0.40377328966699244],
 'f': [1.8194968077812395, 0.21631508488338827],
 'b': [1.236057293434599, 0.7356219385429031],
 'e': [2.876828575670631, -0.200895274247215]}

G3.show(pos=posG3,vertex_color=boje3)

Graf $G_3$ je kritični graf jer je $G_3=K_2\vee C_5$ pri čemu je $K_2=G_3[\{f,g\}]$ i $C_5=G_3[\{a,b,c,d,e\}]$.

G3.show(pos=posG3, edge_colors={'blue':[('a','b'),('b','c'),('c','d'),('d','e'),('e','a')], 
                                'red':[('f','g')],})

jedno bojanje bridova s minimalnim brojem boja

G3.show(edge_colors=edge_coloring(G3,hex_colors=True))