随机图论基础

  • 开发
  • 45

一，随机图、随机图空间

1，随机图

一个n个点的无向图，最多有s=n(n-1)/2条边。

假设每条边都有p的概率是存在的，有1-p的概率是不存在的，那么一个有k条边的图出现的概率是p^k(1-p)^{s-k}

2，随机图空间

所有有k条边的图出现的概率总和是\binom{s}{k}p^k(1-p)^{s-k}

所有图出现的概率总和是\sum _{0<=k<=s}\binom{s}{k}p^k(1-p)^{s-k}=1

每个图看作一个点，所有的图构成一组互斥事件，总概率是1，这样就构成一个概率空间，记做G(n,p)

3，简单规律

对于G(n,0)，空图以1的概率出现，其他图概率是0

对于G(n,1)，完全图以1的概率出现，其他图概率是0

二，条件概率空间

给定n和一个有k条边的图，对于不同的概率p，该图的出现概率p^k(1-p)^{s-k}有不同的取值。

当p=k/s时，概率p^k(1-p)^{s-k}取到最大值。

阅读全部

相关推荐

  2. 代码随想录：图论_01基础

    2024-02-01 21:00:04       24 阅读

  4. 图论基础入门

    2024-02-01 21:00:04       30 阅读

最近更新

  3. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-02-01 21:00:04       94 阅读

  4. Could not load dynamic library ‘cudart64_100.dll‘

    2024-02-01 21:00:04       100 阅读

  9. 在Django里面运行非项目文件

    2024-02-01 21:00:04       82 阅读

  19. Python语言-面向对象

    2024-02-01 21:00:04       91 阅读

  20. 如何分清楚常见的 Git 分支管理策略Git Flow、GitHub Flow 和 GitLab Flow

    2024-02-01 21:00:04       85 阅读

热门阅读

  2. tar解压之后属主和属组不是当前用户问题

    2024-02-01 21:00:04       53 阅读

  9. 台达dvp16es2plc-qt串口通信协议

    2024-02-01 21:00:04       51 阅读
  11. C++入门

    C++入门

    2024-02-01 21:00:04      36 阅读

  15. 项目解决方案：市小区高清视频监控平台联网整合设计方案(下)

    2024-02-01 21:00:04       49 阅读

  17. 2024美赛数学建模D题思路+模型+代码+论文（持续更新）

    2024-02-01 21:00:04       57 阅读

  19. 使用android辅助服务监听Activity打开

    2024-02-01 21:00:04       45 阅读

  22. 被审查？ChatGPT陷入数据风波！

    2024-02-01 21:00:04       48 阅读

  24. （蓝桥杯每日一题）游戏最优解及求二进制中有多少1

    2024-02-01 21:00:04       50 阅读

  26. M1芯片MAC 安装MySQL、Nacos遇到的问题

    2024-02-01 21:00:04       62 阅读

  30. 【SpringBoot】如何在 Utils 工具类中注入 Bean

    2024-02-01 21:00:04       50 阅读