El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
HOME Els meus cursos Finalitzats
◄ Anterior
◄

Algoritmes d'Aparellament en Grafs

Següent ►
►

Introducció

Els algoritmes d'aparellament en grafs són tècniques utilitzades per trobar conjunts de parelles d'arestes en un graf, de manera que no comparteixin cap vèrtex. Aquest tipus de problemes són comuns en diverses aplicacions, com ara l'assignació de tasques, la planificació de recursos i la resolució de problemes de xarxes.

Conceptes Bàsics

Definicions Clau

  • Aparellament (Matching): Un conjunt d'arestes en un graf on cap parell d'arestes comparteix un vèrtex comú.
  • Aparellament màxim (Maximum Matching): Un aparellament que conté el nombre màxim possible d'arestes.
  • Aparellament perfecte (Perfect Matching): Un aparellament on tots els vèrtexs del graf estan aparellats.
  • Aparellament maximal (Maximal Matching): Un aparellament que no es pot ampliar afegint més arestes.

Exemples

Considerem el següent graf:

A - B
|   |
C - D
  • Un aparellament podria ser {A-B, C-D}.
  • Un aparellament màxim també podria ser {A-B, C-D}, ja que no hi ha més arestes per afegir.
  • Un aparellament perfecte és el mateix que l'aparellament màxim en aquest cas.
  • Un aparellament maximal podria ser {A-B}, ja que no es pot afegir més arestes sense compartir vèrtexs.

Algoritmes Clau

Algoritme de Greedy

L'algoritme de Greedy és una tècnica senzilla per trobar un aparellament maximal. No garanteix trobar l'aparellament màxim, però és ràpid i fàcil d'implementar.

Pseudocodi

1. Inicialitza l'aparellament M com a buit.
2. Ordena les arestes del graf en ordre arbitrari.
3. Per a cada aresta (u, v) en l'ordre:
   a. Si ni u ni v estan aparellats en M:
      i. Afegeix (u, v) a M.
4. Retorna M.

Implementació en Python

def greedy_matching(graph):
    matching = set()
    matched_vertices = set()
    
    for u, v in graph.edges():
        if u not in matched_vertices and v not in matched_vertices:
            matching.add((u, v))
            matched_vertices.add(u)
            matched_vertices.add(v)
    
    return matching

# Exemple d'ús
import networkx as nx

G = nx.Graph()
G.add_edges_from([(1, 2), (2, 3), (3, 4), (4, 1), (1, 3)])
print(greedy_matching(G))

Algoritme de Kuhn-Munkres (Hungarian Algorithm)

Aquest algoritme és utilitzat per trobar l'aparellament màxim en grafs bipartits. És més complex que l'algoritme de Greedy, però garanteix trobar l'aparellament màxim.

Pseudocodi

1. Inicialitza l'aparellament M com a buit.
2. Per a cada vèrtex u en el conjunt U:
   a. Si u no està aparellat:
      i. Realitza una cerca augmentant per trobar un camí augmentant.
      ii. Si es troba un camí augmentant, actualitza M.
3. Retorna M.

Implementació en Python

def bpm(u, matchR, seen, bpGraph):
    for v in range(len(bpGraph[0])):
        if bpGraph[u][v] and not seen[v]:
            seen[v] = True
            if matchR[v] == -1 or bpm(matchR[v], matchR, seen, bpGraph):
                matchR[v] = u
                return True
    return False

def maxBPM(bpGraph):
    matchR = [-1] * len(bpGraph[0])
    result = 0
    for i in range(len(bpGraph)):
        seen = [False] * len(bpGraph[0])
        if bpm(i, matchR, seen, bpGraph):
            result += 1
    return result

# Exemple d'ús
bpGraph = [[0, 1, 1, 0, 0, 0],
           [1, 0, 0, 1, 0, 0],
           [0, 0, 1, 0, 0, 1],
           [0, 0, 0, 0, 1, 0],
           [0, 0, 0, 1, 0, 0],
           [0, 0, 0, 0, 0, 1]]

print("El nombre màxim d'aparellaments és", maxBPM(bpGraph))

Exercicis Pràctics

Exercici 1: Aparellament Greedy

Donat el següent graf, implementa l'algoritme de Greedy per trobar un aparellament maximal.

A - B
|   |
C - D
|   |
E - F

Solució

G = nx.Graph()
G.add_edges_from([('A', 'B'), ('A', 'C'), ('C', 'D'), ('D', 'E'), ('E', 'F')])
print(greedy_matching(G))

Exercici 2: Aparellament Màxim en Graf Bipartit

Donat el següent graf bipartit, implementa l'algoritme de Kuhn-Munkres per trobar l'aparellament màxim.

U = {1, 2, 3}
V = {4, 5, 6}
Edges = {(1, 4), (1, 5), (2, 5), (3, 6)}

Solució

bpGraph = [[1, 1, 0],
           [0, 1, 0],
           [0, 0, 1]]

print("El nombre màxim d'aparellaments és", maxBPM(bpGraph))

Resum

En aquesta secció, hem explorat els conceptes bàsics dels algoritmes d'aparellament en grafs, incloent-hi les definicions clau i els algoritmes més utilitzats com el Greedy i el Kuhn-Munkres. També hem proporcionat exemples pràctics i exercicis per reforçar els conceptes apresos. Amb aquests coneixements, estàs preparat per abordar problemes d'aparellament en grafs en aplicacions reals.

◄ Anterior
◄
Següent ►
►
El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
© Copyright 2024. Tots els drets reservats