Matroide: differenze tra le versioni

Si osservi che in questo modo si ottiene una matroide anche da un multigrafo infinito; una tale matroide è finitaria perché tutti i cicli sono finiti; inoltre essa è finito-dimensionale se il numero dei vertici è finito, anche se il numero degli spigoli è infinito).

 

 

Consideriamo, all'opposto, una situazione che non porta ad una matroide. Sia ''E'' l'insieme dei nodi di un grafo e chiamiamo insiemi di nodi indipendenti quelli che possono essere colorati con non più di tre colori senza coincidenze fra nodi adiacenti. L'insieme vuoto soddisfa alla condizione e ogni sottoinsieme di nodi tricolorabile è tricolorabile; non vale invece la proprietà di scambio, in quanto si possono avere due sottografi massimali tricolorabili con diversi numeri di nodi, come mostrato nella figura alla destra.