ノードとノードの間のエッジの有無を，隣接行列を用いて表す。ある無向グラフの隣接行列が次の場合，グラフで表現したものはどれか。ここで，ノードを隣接行列の行と列に対応させて，ノード間にエッジが存在する場合は1で，エッジが存在しない場合は0で示す。
出典令和元年度 秋期 基本情報技術者試験 午前 問3
隣接行列から無向グラフを特定する方法
隣接行列の1から得られる辺$a-b,b-c,b-d,c-d,c-e,e-f$を過不足なく持つグラフはウです。 行列は対称なので無向グラフです。上三角部分の1だけを拾うと辺は$a-b$、$b-c$、$b-d$、$c-d$、$c-e$、$e-f$の6本になり、これと完全に一致するのがウです。 辺$b-c$がなく、代わりに行列にない辺$d-e$があります。 辺$c-d$がなく、代わりに行列にない辺$d-e$があります。 必要な6本に加えて、行列では0である$d-e$まで結ばれています。