Los problemas NP-completos en grafos, como la enumeración y la selección de subgrafos con características dadas, se vuelven especialmente relevantes para grafos grandes y redes. Aquí se proponen declaraciones particulares con restricciones para resolver tales problemas, y se distinguen subclases de grafos. Proponemos una clase de grafos prefractales y revisamos declaraciones particulares de problemas NP-completos. Como ejemplo, se proponen algoritmos para buscar árboles de expansión y empaquetar grafos bipartitos. Los algoritmos desarrollados son polinomiales y se basan en algoritmos bien conocidos y se utilizan en forma de procedimientos. Proponemos usar la clase de grafos prefractales como una herramienta para estudiar problemas NP-completos e identificar condiciones para su resolubilidad. Al utilizar grafos prefractales para modelar grafos y redes grandes, es posible obtener soluciones aproximadas y algunas soluciones exactas para problemas en objetos naturales - redes sociales, redes de transporte, etc.