Números_de_balanceo.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/tonamatos/balanceableGraphs/blob/main/N%C3%BAmeros_de_balanceo.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "zHzdngXHYdvc"
      },
      "outputs": [],
      "source": [
        "from math import factorial\n",
        "import math"
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "def lema_viejo(k,k_p,s,c):\n",
        "  valor = c+(factorial(s) / (factorial(2) * factorial(s - 2))) - (k_p/2) + s*((k/2)+(2*c)-1)\n",
        "  print('El número de aristas rojas era al menos:',valor)\n",
        "  print('\\nEl número de balanceo era:',valor-1)\n",
        "  return\n",
        "\n",
        "def lema(k,k_p,s,c):\n",
        "  valor = c+ (math.comb(s, 2)) - (k_p/2) + s*((k/2)+c-1)\n",
        "  print('El número de aristas rojas es al menos:',valor)\n",
        "  print('\\nEl número de balanceo es:',valor-1)\n",
        "  return "
      ],
      "metadata": {
        "id": "uJ0uahp2YxrW"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "def cota(v,e):\n",
        "  valor = (v-3)*((v+e+2)/2)\n",
        "  print('La cota que debemos preservar es',valor)\n",
        "  return"
      ],
      "metadata": {
        "id": "5kPr13mVVLK6"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "# $H_1$"
      ],
      "metadata": {
        "id": "9TEUd95gfZoX"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "Considerando la subgráfica $K_{1,3}+e$ balanceada"
      ],
      "metadata": {
        "id": "MOZ483lNiUl5"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "k = 6\n",
        "k_p = 4\n",
        "s = 4\n",
        "c = 1\n",
        "lema(k,k_p,s,c)\n",
        "\n",
        "v=6\n",
        "e=6\n",
        "cota(v,e)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "CpKTXGb8Z0Ew",
        "outputId": "65c9c028-a9c1-4c12-a846-64e52f85bdbc"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "El número de aristas rojas es al menos: 17.0\n",
            "\n",
            "El número de balanceo es: 16.0\n",
            "La cota que debemos preservar es 21.0\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "#$H_2$"
      ],
      "metadata": {
        "id": "1Da-vl3DhTh4"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "Considerando la subgráfica $C_4$ balanceada"
      ],
      "metadata": {
        "id": "5rPDmztEidOe"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "k = 6\n",
        "k_p = 4\n",
        "s = 4\n",
        "c = 1\n",
        "lema(k,k_p,s,c)\n",
        "\n",
        "v=6\n",
        "e=6\n",
        "cota(v,e)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "OaxGIqj_hUeF",
        "outputId": "245ec123-3390-43c5-d9cb-9a6ad8b9a09b"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "El número de aristas rojas es al menos: 17.0\n",
            "\n",
            "El número de balanceo es: 16.0\n",
            "La cota que debemos preservar es 21.0\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "#$H_3$"
      ],
      "metadata": {
        "id": "TNLpQAtQjEWz"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "Considerando la subgráfica $P_5$ balanceada"
      ],
      "metadata": {
        "id": "uuIqWCsgjEW0"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "k = 6\n",
        "k_p = 4\n",
        "s = 5\n",
        "c = 1\n",
        "lema(k,k_p,s,c)\n",
        "\n",
        "v=6\n",
        "e=6\n",
        "cota(v,e)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "8dffa530-6d7a-4f33-bb2a-c8317d92c0be",
        "id": "HFhSous6jEW0"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "El número de aristas rojas es al menos: 24.0\n",
            "\n",
            "El número de balanceo es: 23.0\n",
            "La cota que debemos preservar es 21.0\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "#$H_4$"
      ],
      "metadata": {
        "id": "jkOm2h5xjDzX"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "Considerando la subgráfica $K_{1,3}+e$ balanceada"
      ],
      "metadata": {
        "id": "NuJQfh8yjDzX"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "k = 8\n",
        "k_p = 4\n",
        "s = 4\n",
        "c = 2\n",
        "lema(k,k_p,s,c)\n",
        "\n",
        "v=8\n",
        "e=8\n",
        "cota(v,e)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "09631908-5fdb-4608-8e9f-63effb5eeb8f",
        "id": "x0ypcOpTjDzY"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "El número de aristas rojas es al menos: 26.0\n",
            "\n",
            "El número de balanceo es: 25.0\n",
            "La cota que debemos preservar es 45.0\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "#$H_5$"
      ],
      "metadata": {
        "id": "qpyQxO77jDWT"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "Considerando la subgráfica $K_{1,3}+e$ balanceada"
      ],
      "metadata": {
        "id": "bClM5k0xjDWU"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "k = 8\n",
        "k_p = 4\n",
        "s = 4\n",
        "c = 2\n",
        "lema(k,k_p,s,c)\n",
        "\n",
        "v=8\n",
        "e=8\n",
        "cota(v,e)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "5222f0fc-e9a7-4edb-def2-fecd6587174f",
        "id": "ApLPifivjDWU"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "El número de aristas rojas es al menos: 26.0\n",
            "\n",
            "El número de balanceo es: 25.0\n",
            "La cota que debemos preservar es 45.0\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "#$H_6$"
      ],
      "metadata": {
        "id": "nd3MTqDijCte"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "Considerando la subgráfica $P_3$ balanceada"
      ],
      "metadata": {
        "id": "0J8Y4QqnjCtf"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "k = 6\n",
        "k_p = 4\n",
        "s = 4\n",
        "c = 2\n",
        "lema(k,k_p,s,c)\n",
        "\n",
        "v=6\n",
        "e=6\n",
        "cota(v,e)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "eb44c288-8248-4102-c4e8-bcf37c84c807",
        "id": "3ZQamd3cjCtf"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "El número de aristas rojas es al menos: 22.0\n",
            "\n",
            "El número de balanceo es: 21.0\n",
            "La cota que debemos preservar es 21.0\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "#$H_7$"
      ],
      "metadata": {
        "id": "lw0yV3e3jBwq"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "Considerando la subgráfica $K_{1,3}+e$ balanceada"
      ],
      "metadata": {
        "id": "-DRBTi7pjBwq"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "k = 8\n",
        "k_p = 4\n",
        "s = 4\n",
        "c = 2\n",
        "lema(k,k_p,s,c)\n",
        "\n",
        "v=8\n",
        "e=8\n",
        "cota(v,e)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "64675b69-d8e3-4a91-e848-52a0625148c5",
        "id": "8lV0GhFujBwr"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "El número de aristas rojas es al menos: 26.0\n",
            "\n",
            "El número de balanceo es: 25.0\n",
            "La cota que debemos preservar es 45.0\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "#$H_8$"
      ],
      "metadata": {
        "id": "hZ-0swkei_dJ"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "Considerando la subgráfica $H_7$ balanceada"
      ],
      "metadata": {
        "id": "1u6Y1dx1i_dJ"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "k = 10\n",
        "k_p = 8\n",
        "s = 9\n",
        "c = 0\n",
        "lema(k,k_p,s,c)\n",
        "\n",
        "v=10\n",
        "e=10\n",
        "cota(v,e)"
      ],
      "metadata": {
        "id": "INIrIoAki_dK",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "18abfb0d-5a1d-4dca-9799-bdc8479187a3"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "El número de aristas rojas es al menos: 68.0\n",
            "\n",
            "El número de balanceo es: 67.0\n",
            "La cota que debemos preservar es 77.0\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "k = 10\n",
        "(1/2) * math.ceil(k/3) * (math.ceil(k/3)-1)"
      ],
      "metadata": {
        "id": "pGrcSo4fwG5j",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "fe846802-69ed-4e60-d0b6-2c736f10abbc"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "6.0"
            ]
          },
          "metadata": {},
          "execution_count": 7
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [],
      "metadata": {
        "id": "kpg1Pxucrz6d"
      },
      "execution_count": null,
      "outputs": []
    }
  ]
}