from itertools import *

g = graphs.CompleteGraph(4)

permutations = list(product([0,1],repeat=6)) 
edges = g.edges()

def rainbow_plot(g, edges, perm, prob_red, event_flag):
    edge_colors = {}
    edge_colors['blue'] = [e for i, e in enumerate(edges) if perm[i] == 1]
    edge_colors['red'] = [e for i, e in enumerate(edges) if perm[i] == 0]
    
    nreds = len(edge_colors['red'])
    nblues = len(edge_colors['blue'])

    prob = (prob_red ** nreds) * ((1 - prob_red) ** nblues)
    T = text(f"{prob:.4f}", (0, -2), axes=False, color='black')
    if (event_flag):
        T = text(f"{prob:.4f}", (0, -2), axes=False, color='black', background_color='#7bf689')
        return g.plot(vertex_size=55, vertex_labels=False, edge_thickness=3, edge_colors=edge_colors, figsize=(1, 1))  + T, prob
    else:
        return g.plot(vertex_size=55, vertex_labels=False, edge_thickness=3, edge_colors=edge_colors, figsize=(1, 1))  + T, prob
    
def sample_space_plot(prob_red, event=None):

    plots = []
    current = []
    event_prob = 0
    for i, p in enumerate(permutations):

        red_edges = [e for i, e in enumerate(edges) if p[i] == 0]
        blue_edges = [e for i, e in enumerate(edges) if p[i] == 1]

        red_graph = Graph(4)
        red_graph.add_edges(red_edges)

        blue_graph = Graph(4)
        blue_graph.add_edges(blue_edges)

        event_flag = False
        if event:
            event_flag = event(red_graph, blue_graph)

        if i % 8 == 0 and i != 0:
            plots.append(current)
            current = []

        plot, prob = rainbow_plot(g, edges, p, prob_red, event_flag)

        if event and event_flag:
            event_prob += prob

        current.append(plot)

    plots.append(current)

    return graphics_array(plots).show(figsize=(7, 7)), event_prob

Espaços amostrais

Experimento: pintar as arestas do $K_4$ aleatoriamente

Distribuição uniforme

• probabilidade de uma aresta ser vermelha: 0.5
• probabilidade de uma aresta ser azul: 0.5

plot, _ = sample_space_plot(.5)
plot

Distribuição Enviesada

• probabilidade de uma aresta ser vermelha: $2/3$
• probabilidade de uma aresta ser azul: $1/3$

plot, _ = sample_space_plot(2.0/3.0)
plot

Distribuição Tipo Eleição Venezuelana

• probabilidade de uma aresta ser vermelha: $1$
• probabilidade de uma aresta ser azul: $0$

plot, _ = sample_space_plot(1)
plot

Eventos

def has_red_c4(RedGraph, BlueGraph):

    H = graphs.CycleGraph(4)
    return H.is_subgraph(RedGraph, up_to_isomorphism=True)

def has_red_c3(RedGraph, BlueGraph):

    H = graphs.CycleGraph(3)
    return H.is_subgraph(RedGraph, up_to_isomorphism=True)

def red_and_blue_bipartite(RedGraph, BlueGraph):
    
    return RedGraph.is_bipartite() and BlueGraph.is_bipartite()

Existir um $C_4$ vermelho

plot, prob = sample_space_plot(2.0/3.0, has_red_c4)
print(f"Probabilidade do Evento: {prob}")
plot

Probabilidade do Evento: 0.0658436213991769

Existir um $C_3$ vermelho

plot, prob = sample_space_plot(2.0/3.0, has_red_c3)
print(f"Probabilidade do Evento: {prob}")
plot

Probabilidade do Evento: 0.658436213991769

Grafo Vermelho e Azul serem bipartidos

plot, prob = sample_space_plot(0.5, red_and_blue_bipartite)
print(f"Probabilidade do Evento: {prob}")
plot

Probabilidade do Evento: 0.281250000000000

Soma das probabilidades do espaço amostral

def evento_all(RedGraph, BlueGraph):
    return True

plot, prob = sample_space_plot(0.5, evento_all)
print(f"Probabilidade do Evento: {prob}")
plot

Probabilidade do Evento: 1.00000000000000

O método probabilístico

Pergunta: Será que existe uma coloração na qual o grafo vermelho é bipartido e o azul é desconexo?

$$ A = \{\chi_G \in \Omega \colon \textrm{o grafo vermelho é bipartido e o azul é desconexo} \} $$

• Se $\mathbb{P}(A) > 0$, então existe!
• Se $\mathbb{P}(\bar{A}) < 1$, então também existe!
  • Se $\mathbb{P}(\bar{A}) < 1$, então $\mathbb{P}(A) = 1 - \mathbb{P}(\bar{A}) > 0$!

def evento_a_barra(RedGraph, BlueGraph):
    return RedGraph.is_bipartite() == False or BlueGraph.is_connected() == True

plot, prob = sample_space_plot(0.5, evento_a_barra)
print(f"Probabilidade do Evento: {prob}")
plot

Probabilidade do Evento: 0.890625000000000