加权一阶模型计数问题 (WFOMC) 旨在计算给定一阶逻辑语句在给定域上的模型的加权和。对于来自具有计数量词的双变量片段（称为 C²）的语句，它可以在域大小的多项式时间内求解。已知当通过以下公理之一扩展 C² 时，这种多项式时间复杂度得以保留：线性序公理、树公理、森林公理、有向无环图公理或连通性公理。一个有趣的问题仍然是还可以以这种方式向一阶语句中添加哪些其他公理。我们通过将 WFOMC 与图多项式关联起来，为这个问题提供了一个新的视角。利用 WFOMC，我们为一阶逻辑语句定义了弱连通性多项式和强连通性多项式。事实证明，这些多项式具有以下有趣的性质。首先，对于来自 C² 的语句，它们可以在域大小的多项式时间内计算。其次，我们可以用它们来解决所有已知易处理的公理以及新的公理（例如二分性、强连通性、具有 k 个连通分量等）的 WFOMC。第三，著名的 Tutte 多项式可以作为弱连通性多项式的特例恢复，严格和非严格有向色多项式可以从强连通性多项式中恢复。