Для построения скелета графа G^=(X^,U^) необходимо выполнить следующие шаги:
1. Сформируйте множество всех вершин X^, добавив координаты всех вершин из множества X, которые встречаются в ребрах из множества U. В данном случае X = {x1, x2, x3, x4}, и есть ребра, содержащие вершины x2 и x4, поэтому X^ = {x1, x2, x3, x4}.
2. Сформируйте множество всех ребер U^ скелета, добавив в него все ребра из множества U, но заменив каждое ребро (xi xj¯¯¯¯¯¯¯¯¯¯) на две вершины (xi^, xj^). Таким образом, U^={(x1x2^),(x1x3^),(x1x4^),(x3x2^),(x3x4^)}.
3. Постройте граф G^=(X^,U^), соединив каждую пару вершин (xi^, xj^) ребром, если она содержится в множестве U^. В результате получим граф G^.
Граф G^=(X^,U^) для данного случая будет выглядеть следующим образом:
X^ = {x1, x2, x3, x4}
U^ = {(x1x2^),(x1x3^),(x1x4^),(x3x2^),(x3x4^)}
Таким образом, скелет графа G=(X,U) будет выглядеть как G^=(X^,U^), где X^ = {x1, x2, x3, x4}, U^ = {(x1x2^),(x1x3^),(x1x4^),(x3x2^),(x3x4^)}.