Uma dúvida que não lembro se foi sanada na aula... mas é o seguinte.
Sei que nem sempre todo emparelhamento maximal é máximo, mas e o caso do grafo com 1 e 2 arestas?
Para 1 aresta, o emparelhamento maximal é igual ao máximo? (|M|=|M*|=1)
E para 2 arestas, é a mesma coisa? (|M|=|M*|=1)
Se um grafo tiver 2 arestas, um emparelhamento máximo pode ter tamanho 1 ou 2. E qualquer emparelhamento num grafo desses é maximal se e somente se for máximo.
Mas isso já não é verdade num grafo com 3 arestas.
Mas isso já não é verdade num grafo com 3 arestas.
Obrigada por esclarecer Gabriel.... mas e para o grafo com apenas 1 aresta? O conceito de emparelhamento se aplica a ele?
Ou a definição de emparelhamento só vale a partir de 2 arestas?
Ou a definição de emparelhamento só vale a partir de 2 arestas?
A definição de emparelhamento que está nas notas de aula se aplica para grafos com qualquer número de arestas.
Eu não comentei sobre o caso em que m(G) = 1 porque não tinha nenhuma ressalva ao que você tinha dito.
Eu não comentei sobre o caso em que m(G) = 1 porque não tinha nenhuma ressalva ao que você tinha dito.