In graph theory, a branch of mathematics, many important families of graphs can be described by a finite set of individual graphs that do not belong to the family and further exclude all graphs from the family which contain any of these forbidden graphs as (induced) subgraph or minor. A prototypical example of this phenomenon is Kuratowski's theorem, which states that a graph is planar (can be drawn without crossings in the plane) if and only if it does not contain either of two forbidden graphs, the complete graph K5 and the complete bipartite graph K3,3. For Kuratowski's theorem, the notion of containment is that of graph homeomorphism, in which a subdivision of one graph appears as a subgraph of the other. Thus, every graph either has a planar drawing (in which case it belongs to the family of planar graphs) or it has a subdivision of at least one of these two graphs as a subgraph (in which case it does not belong to the planar graphs). (en)
En teoría de grafos, una rama de las matemáticas, muchas familias importantes de grafos se pueden describir mediante un conjunto finito de grafos individuales que no pertenecen a la familia y además excluyen todos los grafos de la familia que contienen cualquiera de estos grafos prohibidos como subgrafos o menores (inducidos). Un ejemplo prototípico de este fenómeno es el teorema de Kuratowski, que establece que un grafo es plano (es decir, se puede dibujar sin cruces en el plano) si y solo si no contiene ninguno de los dos grafos prohibidos, el grafo completo K5 y el grafo bipartito completo K3,3. Para el teorema de Kuratowski, la noción de contener es la del homeomorfismo de grafos, en la que una subdivisión de un grafo aparece como subgrafo del otro. Así, todo grafo o bien tiene un dibujo plano (en cuyo caso pertenece a la familia de los grafos planos) o tiene una subdivisión de al menos uno de estos dos grafos como subgrafo (en cuyo caso no pertenece a los grafos planos). (es)
Характеризация запрещёнными графами — это метод описания семейства графов или гиперграфов путём указания подструктур, которым запрещено появляться внутри любого графа в семействе. (ru)
Характериза́ція заборо́неними гра́фами — це метод опису сімейства графів або гіперграфів вказанням підструктур, яким заборонено з'являтися всередині будь-якого графа сімейства. (uk)
Характеризация запрещёнными графами — это метод описания семейства графов или гиперграфов путём указания подструктур, которым запрещено появляться внутри любого графа в семействе. (ru)
Характериза́ція заборо́неними гра́фами — це метод опису сімейства графів або гіперграфів вказанням підструктур, яким заборонено з'являтися всередині будь-якого графа сімейства. (uk)
In graph theory, a branch of mathematics, many important families of graphs can be described by a finite set of individual graphs that do not belong to the family and further exclude all graphs from the family which contain any of these forbidden graphs as (induced) subgraph or minor. (en)
En teoría de grafos, una rama de las matemáticas, muchas familias importantes de grafos se pueden describir mediante un conjunto finito de grafos individuales que no pertenecen a la familia y además excluyen todos los grafos de la familia que contienen cualquiera de estos grafos prohibidos como subgrafos o menores (inducidos). (es)