Caminho de Largura
Em teoria dos grafos, uma decomposição de caminho de um grafo G é, informalmente, uma representação de G como um caminho "alargado",[1] e a largura de caminho de G é um número que mensura quanto o caminho foi ampliado em largura a partir de G. Mais formalmente, decomposição de caminho é uma sequência de subconjuntos de vértices de G em que os nós extremos de cada aresta apareçam em um dos subconjuntos e que cada vértice apareça em uma subsequência adjacente dos subconjuntos,[2] e o caminho de largura é um a menos que o tamanho do maior conjunto em dada decomposição. Caminho de largura é também conhecida como largura de intervalo (um a menos que o tamanho do clique máximo em um supergrafo de intervalo de G), número de separação de vértice, ou número de busca de nós.[3] Caminho de largura é também conhecida como largura de intervalo (um a menos que o tamanho do clique máximo em um supergrafo de intervalo de G), número de separação de vértice, ou número de busca de nós.